题解 | #表达式求值#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 返回表达式的值
 * @param s string字符串 待计算的表达式
 * @return int整型
 */


int solve(char* s ) {
    // write code here
    // 逆波兰转换，将中缀表达式转换成后缀表达式
    int topIdx = 0; // 作为符号栈的栈顶索引值
    char operator[100] = {0}; // 符号栈
    char temp[100][10] = {0}; 
    int m = 0, j = 0;
    int len = strlen(s);
    for(int i = 0; i < len ; i++) {
        // 如果遇到乘号或者左括号，直接压入符号栈
        if(s[i] == '*' || s[i] == '(') {
            operator[topIdx++] = s[i];
            // 如果遇到加减法
        } else if(s[i] == '+' || s[i] == '-') {
            // 判断栈顶符号是否是乘号，如果是乘号
            if(operator[topIdx - 1] == '*') {
                // 当栈顶符号不为左括号或者栈空时
                while(operator[--topIdx] != '(' && topIdx >= 0) {
                    // 我们将栈顶的符号倒入temp数组中
                    temp[j++][0] = operator[topIdx];
                }
                // 然后将栈顶的符号设为s[i]
                operator[++topIdx] = s[i];
                // 然后移动栈顶索引到下一个位置，方便下一个符号入栈
                topIdx++;
            }
            else {
                // 对于栈顶符号不是乘号的情况，我们直接将符号入栈
                operator[topIdx++] = s[i];
            }
            // 如果遇到右括号
        } else if(s[i] == ')') {
            // 如果栈顶符号不是左括号或者空的时候
            while(operator[--topIdx] != '(' && topIdx >= 0) {
                // 我们将栈中的左括号之后的符号都倒入temp栈中
                temp[j++][0] = operator[topIdx];
            }
            // 如果不是加减乘括号，就是数字
        } else {
            temp[j][m++] = s[i];
            // 如果下一位不是数字了，那么j索引加一方便接收下一个数字
            // m索引变为0，从0开始接收数字
            if((s[i + 1] < '0' || s[i + 1] > '9') && i < len -1) {
                j++;
                m = 0;
                // 如果下一位没有（到达字符串结尾），那么j索引加1
            } else if(i == len - 1) {
                j++;
            }
        }
    }
        // 逆波兰表达式中，出现连续的减号时，除了第一个减号剩余的减号都要转换成加号。
        for(int i = 0, j = 1; i < topIdx; i++) {
            if(operator[i] == '-') {
                while(operator[i + j] == '-' && (i + j) < topIdx) {
                    operator[i + j++] = '+';
                }
            }
        }

        int lenoftemp = 0;
        if(topIdx != 0) {
            for(int i = topIdx - 1; i >= 0; i--) {
                // 将所有符号栈中剩余的符号都倒入temp栈中
                temp[j++][0] = operator[i];
            }
            lenoftemp = j;
        }


    // 用逆波兰表达式求解最终结果
    int result = 0;
    int integer[100];
    for(int i = 0, topIdx = 0; i < lenoftemp; i++) {
        // 如果遇到什么符号，我们执行什么运算
        // 注意是先加入栈的数字，减去后加入栈的数字
        if(strcmp(temp[i], "+") == 0) {
            result = integer[topIdx - 2] + integer[topIdx - 1];
            topIdx--;
            integer[topIdx - 1] = result;
        } else if(strcmp(temp[i], "*") == 0) {
            result = integer[topIdx - 2] * integer[topIdx - 1];
            topIdx--;
            integer[topIdx - 1] = result;
        } else if(strcmp(temp[i], "-") == 0) {
            result = integer[topIdx - 2] - integer[topIdx - 1];
            topIdx--;
            integer[topIdx - 1] = result;
            // 如果遇到了数字，我们将数字放入一个新的integer栈中
        } else {
            integer[topIdx++] = atoi(temp[i]);
        }
    }

    return integer[0];
}