用栈计算中缀表达式（c++实现）

淩亂°似流年 2023-09-28 17:11 10阅读 0赞

## 场景： ##

`例如：用栈计算5-(7*(5-3)+2)*3的值`

--------------------

## 代码： ##

`提示：需要构建数字栈和符号栈两个栈实现，注意优先级的比较：```

#include <iostream>
    #include <map>
    using namespace std;
    #define MAXSIZE 100
    void calculate(const char arr[], int length);
    bool isCompare(char a, char b);
    static map<char,int> kv;
    void cal(int numStack[], const char opStack[], int &top_num, int &top_op);
    void initX();
    
    int main(){
        initX();
        char arr[] = {'5','-','(','7','*','(','5','-','3',')','+','2',')','*','3'};
        int length = sizeof (arr);
        calculate(arr, length);
        return 0;
    }
    
    void calculate(const char arr[], int length){
        int numStack[MAXSIZE];
        char opStack[MAXSIZE];
        int top_num = -1;
        int top_op = -1;
        for(int i=0;i<length;i++){
            if('1'<=arr[i] && arr[i]<='9'){
                numStack[++top_num] = arr[i] - '0';
            }else if(arr[i]=='+' || arr[i]=='-' || arr[i]=='*' || arr[i]=='/'){
                if(top_op==-1 || isCompare(arr[i], opStack[top_op])){
                    opStack[++top_op] = arr[i];
                }else{
                    cal(numStack, opStack, top_num, top_op);
                    opStack[++top_op] = arr[i];
                }
            }else if(arr[i]=='('){
                opStack[++top_op] = arr[i];
            }else if(arr[i]==')'){
                while(opStack[top_op]!='(') {
                    cal(numStack, opStack, top_num, top_op);
                }
                top_op--;
            }
        }
        while(top_op>-1){
            cal(numStack, opStack, top_num, top_op);
        }
        cout << "计算结果：" << numStack[top_num--] << endl;
    }
    
    bool isCompare(char a, char b){
        return kv.find(a)->second > kv.find(b)->second;
    }
    
    void initX(){
        kv['+'] = 1;
        kv['-'] = 1;
        kv['*'] = 2;
        kv['/'] = 2;
    }
    
    void cal(int numStack[], const char opStack[], int &top_num, int &top_op){
        int a,b;
        char op = opStack[top_op--];
        switch(op){
            case '+':
                a = numStack[top_num--];
                b = numStack[top_num--];
                numStack[++top_num] = b+a;
                break;
            case '-':
                a = numStack[top_num--];
                b = numStack[top_num--];
                numStack[++top_num] = b-a;
                break;
            case '*':
                a = numStack[top_num--];
                b = numStack[top_num--];
                numStack[++top_num] = b*a;
                break;
            case '/':
                a = numStack[top_num--];
                b = numStack[top_num--];
                numStack[++top_num] = b/a;
                break;
            default:
                return;
        }
    }

--------------------

## 结果截图： ##

![9d212feb7b254f9f96f650da4d7c631b.png][]

[9d212feb7b254f9f96f650da4d7c631b.png]: https://img-blog.csdnimg.cn/9d212feb7b254f9f96f650da4d7c631b.png