【题解】【递归、栈】四则运算计算器

设计一个程序，对输入的以#为结束的算术表达式（包括+，-，*，/，(，) ），首先判断表达式是否含有非法字符（即非+，-，*，/， (，) 之外的字符），

如果含有非法字符，则报错误信息；如果正确，计算并输出这个表示式的值。

本题希望利用算符优先关系，实现对算术四则混合运算表达式的求值。

【输入格式】

以#为结束符的算术表达式。

【输出格式】

对于每组测试数据算术表达式，如果含有非法字符，输出“NO”，否则输出表达式的值，行尾不得有多余的空格。

【样例输入】

3+4*(5-3)#

【样例输出】

11

【样例说明】

　　输入样例是合法的表达式，因此求表达式的值，并输出11。

【样例输入】

3+;4*(5-3)#

【样例输出】

NO

【样例说明】

输入样例含不合法的字符';'，因此输出“NO”。

#include <iostream>
#include <string>
#define isNumber(a) (a >= '0' && a <= '9')
using namespace std;
bool validJudge(const char& ch) {
    return (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')' || isNumber(ch));
}
char* s;
int tr(int pre, char oper = 0) {
    int now;
    if (*s == '#') return pre;                  // 计算结束
    else if (*s == ')') { s++; return pre; }    // 遇到右括号就返回，完成括号内的计算
    else if (*s == '(') { s++; now = tr(0); }   // 将括号里面的计算完之后再继续
    else if (isNumber(*s)) { now = atoi(s); while (isNumber(*s)) s++; } // 读取到一个数字
    else {                                      // 读取到一个运算符
        switch (oper = *s, ++s, oper) {         // 这里oper用不到所以借用了oper,使得无需每种case都加上s++语句
            case '+': return tr(pre, '+');      // 加法延迟到下一次来判断，防止后面的数字是别人的乘数
            case '-': return tr(pre, '-');      // 减法延迟同理
            case '*': return tr(pre, '*');      // 乘法延迟仅仅为了复用读取数字的代码，实际上此处可直接读取后面数字或括号，然后直接在此处相乘
            case '/': return tr(pre, '/');      // 除法延迟同理
        }
    }
    switch (oper) {                             // 读取数字之后在此处进行运算
        case '+': return pre + tr(now);         // now后面可能有乘号，需要先计算后面
        case '-': return pre + tr(-now);        // 减法相当于加法
        case '*': return tr(pre * now);         // 乘法优先级高，可直接相乘，相乘后合并为一个数字继续往后计算，与加减不同，加减为倒序，乘除为顺序
        case '/': return tr(pre / now);         // 除法同理
        default:  return tr(now);               // 前面没有运算符，可能该数字为最开始的数字，或者前面为左括号
    }
}
int main() {
    string ss;
    getline(cin, ss);
    for (int i = 0, len = ss.size() - 1; i < len; i++) {
        if (!validJudge(ss[i])) {
            cout << "NO";
            return 0;
        }
    }
    if (ss.back() != '#') {
        cout << "NO";
        return 0;
    }
    s = &ss[0];
    cout << tr(0);
    return 0;
}

更多测试样例：

(((1+1)*(2+3)/(9-2))+10)*10#
110

((1+1)*2)*2#
8

((1+(1+1))*2#
6

1+1-3#
-1

3*(4-1*2)+6/(1+1)#
9

3*(2-1)+1#
4

10*5-2/2+4#
53