题解 | #表达式求值#C语言实现

解题思路：1.将普通表达式转化为逆波兰表达式。2.计算逆波兰表达式的值。

1.将普通表达式转化为逆波兰表达式：使用字符串存储操作符、数值，形成字符串数组存储逆波兰表达式。从左到右遍历输入的字符串，如果是数字，直接存入字符串数组；如果是*，直接入栈；如果是（也直接入栈；如果是+或-，判断栈顶元素，如果不是（，则栈顶元素出栈，当前符号入栈；如果是），出栈直至遇到（。若遍历结束，栈不为空，则逐个出栈。

2.计算逆波兰表达式的值：以字符串数组作为输入，逐个读取，计算逆波兰表达式的值。

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 返回表达式的值
 * @param s string字符串 待计算的表达式
 * @return int整型
 */
#include <stdio.h>
int solve(char* s ) {
    //二维数组存储逆波兰表达式
    char exp[100][10] = {0};
    int exp_p = 0;

    //栈
    char op[100];
    int op_top = 0;

    //转换逆波兰表达式
    int i = 0;
    while (s[i] != '\0') {
        if (s[i] == '*') {//高优先级，直接入栈
            op[op_top++] = s[i];
        } else if (s[i] == '+' || s[i] == '-') { //低优先级判断
            if (op_top > 0) {//栈不为空，则检查栈顶符号
                if (op[op_top - 1] !=
                        '(') {//若优先级不大于栈顶符号，则出栈并替换
                    sprintf(exp[exp_p], "%c", op[op_top - 1]);
                    exp_p++;
                    op[op_top - 1] = s[i];
                } else {//否则入栈
                    op[op_top++] = s[i];
                }
            } else {//栈空，直接入栈
                op[op_top++] = s[i];
            }
        } else if (s[i] == '(') { //（直接入栈
            op[op_top++] = s[i];
        } else if (s[i] == ')') { //）出栈，直到遇见）
            if (op_top > 0) { //判断栈是否为空
                while (op[op_top - 1] != '(') { //循环出栈
                    sprintf(exp[exp_p], "%c", op[op_top - 1]);
                    exp_p++;
                    op_top--;
                }
                op_top--;//（出栈
            }
        } else {//如果是数值
            int j = 0;
            while (s[i] >= '0' && s[i] <= '9') { //循环读入数值
                exp[exp_p][j++] = s[i++];
            }
            exp[exp_p][j] = '\0';
            exp_p++;
            continue;
        }
        i++;
    }

    while (op_top > 0) { //如果栈不为空，全部出栈
        sprintf(exp[exp_p], "%c", op[op_top - 1]);
        exp_p++;
        op_top--;
    }

    for (int i=0; i<exp_p; i++) {
        printf("%s\n",exp[i]);
    }

    //逆波兰表达式结果计算
    int num[100], num_top = 0;
    for (int i = 0; i < exp_p; i++) {
        if (strcmp(exp[i], "+") == 0) {
            num[num_top - 2] += num[num_top - 1];
            num_top--;
        }
        else if (strcmp(exp[i], "-") == 0) {
            num[num_top - 2] -= num[num_top - 1];
            num_top--;
        }
        else if (strcmp(exp[i], "*") == 0) {
            num[num_top - 2] *= num[num_top - 1];
            num_top--;
        }else {
            sscanf(exp[i], "%d",&num[num_top]);
            num_top++;
        }
    }

    return num[0];
}