[C++知识库]算数表达式求解（栈）

题目：

我们需要使用C语言的栈思想去实现简易四则运算表达式

样例：

输入：3+4*5/5
输出结果：7

实现思路：

我们需要设置两个栈，一个用来存储数字，一个用来存储符号，遇见数字压入数字栈，遇见符号就比较于符号栈栈顶符号的优先级（初始符号栈中栈顶元素是‘#’，我们设定‘#’的优先级最低），若优先级大于符号栈栈顶的符号就压入符号栈中，若优先级小于或者等于符号栈栈顶的符号就取数字栈中的两个元素使用符号栈栈顶的符号进行计算，并将计算结果再次存入数字栈中

注意的点：

我们用户在输入算式的时候不可能在式子最后再加上一个‘#’号，所以我们应该自己编写程序去自动为用户输入的算式字符串的最后加上一个‘#’字符，目的是保证式子的最后一个运算符可以被用来计算，否则符号栈中最后就会没有小于用户所输入的运算式的最后一个运算符的符号导致式子并没有被算完。

代码如下：

#include <stdio.h>
#include <string.h>
// 设置符号优先级
int compareReturn(char str1) {
    if (str1 == '#') {
        return 0;
    } else if (str1 == '+' || str1 == '-') {
        return 1;
    } else if (str1 == '*' || str1 == '/') {
        return 2;
    } else {
        printf("输入了无效符号");
        return -1;
    }
}
// 计算函数
int jisuan(int x, char str1, int y) {
    int ans = 0;
    if (str1 == '+') {
        ans = x + y;
    } else if (str1 == '-') {
        ans = x - y;
    } else if (str1 == '*') {
        ans = x * y;
    } else if (str1 == '/') {
        ans = x / y;
    }
    return ans;
}
int main(int argc, const char * argv[]) {
    //初始化两个栈
    //第一个栈为数字栈
    //第二个栈为符号栈
    int firstStack [100] = {0};
    int firstTop = -1;
    
    char secondStack [100] = {'#'};
    int secondTop = 0;
    char str[100];
    int flag = -1;
    printf("请输入待计算的算术表达式:\n");
    scanf("%s", str);
    //表达式长度
    int x = 0;
    int length = (int)strlen(str);
    //在用户所输入的式子后面加‘#’号
    str[length] = '#';
    length = length + 1;
    for (int i = 0; i < length;) {
        if (str[i] >= '0' && str[i] <= '9') {
            x *= 10;
            x += str[i++] - '0';
            flag=1;
        } else {
            if(flag==1) {
             firstStack[++firstTop] = x;
             x = 0;
             flag=-1;
            }
            if (compareReturn(secondStack[secondTop]) < compareReturn(str[i])) {
                secondStack[++secondTop] = str[i++];
            } else {
                int b = firstStack[firstTop--];
                int a = firstStack[firstTop];
                firstStack[firstTop] = jisuan(a, secondStack[secondTop], b);
                secondTop--;
                if (str[i] == '#' && secondTop == 0) {
                    break;
                }
            }
        }
    }
    printf("%d", firstStack[firstTop]);
}

最后感谢大佬的博客：大佬博客