题解 | 表达式求值

int calculator(int a, int b, char ch) {
    int res = 0;
    switch (ch) {
        case '+':
            res = b + a;
            break;
        case '-':
            res = b - a;
            break;
        case '*':
            res = b * a;
            break;
    }
    return res;
}
int IN(char ch) {
    if (ch == '+' || ch == '-' || ch == '*' || ch == '(' || ch == ')'||ch =='\0')  {
        return 0;
    } else {
        return 1;//是操作数
    }
}
/*
函数作用比较两个运算符的优先级
a为第一个运算符
bw为第二个运算符
*/
char Precede(char a, char b) {
    if (a == '#') return '<'; //默认第一次的情况！！
    if(b =='\0') return '>'; //需要计算了
    if (b == '+' || b == '-') {
        if (a == '(') {
            return '<'; //这种情况是因为要先计算括号内的！
        } else {
            return '>';
        }
    } else if (b == '*' || b == '/') {
        if (a == '*' || a == '/' || a == ')') {
            return '>';
        } else
            return '<';
    } else if (b == '(') {
        return '<'; //先算括号内的
    } else if (b == ')') {
        if (a == '(') {
            return '=';
        } else {
            return '>';//括号里的最大
        }
    }
    return '<';//不会执行到这里来
}
int solve(char* s ) {
    // write code here
    int i = 0;
    char opt[100] = {0}; //存放运算符
    int  p1 = 0;
    int num[100] = {0}; //存放操作数
    int  p2 = 0;
    opt[p1++] = '#';//一个占位符，相当于是
    while (s[i] != '\0' || opt[p1 - 1] != '#') {
        if (IN(s[i])) {
            int temp2 = 0;
            while (s[i] >= '0' && s[i] <= '9') {
                temp2 = s[i] - '0' + temp2 * 10;
                i++; //这里刚好相当于有i++
            }
            num[p2++] = temp2;//存放结果
        } else { //运算符
            int temp = 0;
            switch (Precede(opt[p1 - 1], s[i])) {
                case '<':
                    //直接入队，当前s[i]的优先级大于栈顶的
                    opt[p1++] = s[i];
                    i++;
                    break;
                case '>':
                    //需要计算了
                    temp = calculator(num[p2 - 1], num[p2 - 2], opt[--p1]);
                    p2 = p2 - 2;
                    num[p2++] = temp;//存放结果
                    break;
                case '=': //这个是专门给（）这种情况做一个匹配的
                    //那就将
                    p1--;//将（这个符号出栈同时读取下一个字符
                    i++;
                    break;
            }
        }
    }
    return num[--p2];
}

这个题目做了很久，就是细节很多地方没有处理好，核心就是考察了栈这种数据结构，就是说利用栈的先进后出的特点，刚好能很好的把这个结果解算出来。

需要特别注意的地方，就是运算优先级的考虑，这个我是直接看数据结构这本书上写的。按照3个规则：

1. 先乘除，后加减
2. 从左到右计算
3. 先括号内，后括号外

也就是说只有当这个优先级发生变化的时候才进行计算，核心代码就是那个switch中那三种情况。