题解 | #表达式求值#中缀表达式C语言求解

中缀表达式，建立两个栈，分别是数字栈和符号栈。

遇到数字直接入栈，

遇到符号栈需要判断，当符号是‘（’时直接入栈；当符号是‘）’时，直接出栈，直到遇到‘（’；遇到高优先级入栈，遇到低优先级出栈。

代码实现如下：

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

//定义数组大小
#define MAXSIZE 100
//判断表达式的优先级，a的优先级高于b返回0，否则返回1；
int symcmp(char a, char b) {
    if (b == '(')
        return 1;
    else if ((b == '*' || b == '/') && (a == '+' || a == '-' || a == '('))
        return 1;
    else if ((b == '+' || b == '-') && (a == '('))
        return 1;
    else
        return 0;
}
//计算运算值栈顶两个元素(a栈顶第一个元素，b栈顶第二个元素)
int calculate(char c, int a, int b) {
    int tmp = 0;
    switch (c) {
        case '+':
            tmp = b + a;
            break;
        case '-':
            tmp = b - a;
            break;
        case '*':
            tmp = b * a;
            break;
        case '/':
            tmp = b / a;
            break;
    }
    return tmp;
}

int solve(char* s ) {
    int num_stack[MAXSIZE]; //运算值栈
    int num_top = -1; //运算值栈指针
    char sym_stack[MAXSIZE]; //操作符栈
    int sym_top = -1; //操作符栈指针
    int i = 0;
    while (s[i] != '\0') {
        if (isdigit(s[i])) {
            //数字进入数字栈
            int val = 0;
            while (isdigit(s[i])) {
                val = val * 10 + s[i] - '0';
                i++;
            }
            num_stack[++num_top] = val;
        } else {
            //符号进入符号栈
            if (s[i] == ')') {
			  //遇到‘）’开始出栈至到遇到‘（’
                while (sym_stack[sym_top] != '(') {
                    int ret = calculate(sym_stack[sym_top], num_stack[num_top],
                                        num_stack[num_top - 1]);
                    sym_top--;
                    num_top -= 2;
                    num_stack[++num_top] = ret;
                }
                sym_top--;
                i++;
            } else if (!symcmp(sym_stack[sym_top], s[i])) {
			  //遇到了+-*/，判断优先级，如果栈顶符号的优先级高，则进行运算
                while (sym_top > -1 && (!symcmp(sym_stack[sym_top], s[i]))) {
                    int ret = calculate(sym_stack[sym_top], num_stack[num_top],
                                        num_stack[num_top - 1]); //计算栈顶两个元素
                    sym_top--;
                    num_top -= 2;
                    num_stack[++num_top] = ret;
                }
                sym_stack[++sym_top] = s[i];
                i++;
            }
            else {
			  //没啥特殊情况，直接入栈
                sym_stack[++sym_top] = s[i];
                i++;
            }
        }
    }
    while (sym_top > -1) {
		//计算栈顶两个元素
		int ret = calculate(sym_stack[sym_top], num_stack[num_top], num_stack[num_top - 1]); 
		sym_top--;
		num_top -= 2;
		num_stack[++num_top] = ret;
    }
    return num_stack[0];
}