数据结构——表达式求值（栈的应用）

先附上老师的代码

//202031061018 刘知鑫
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <unordered_map>

using namespace std;

stack<int> num;
stack<char> op;

void eval()
{
    auto b = num.top();
    num.pop();
    auto a = num.top();
    num.pop();
    auto c = op.top();
    op.pop();
    int x;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;
    num.push(x);
}

int main()
{
    unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i ++ )
    {
        auto c = str[i];
        if (isdigit(c))
        {
            int x = 0, j = i;
            while (j < str.size() && isdigit(str[j]))
                x = x * 10 + str[j ++ ] - '0';
            i = j - 1;
            num.push(x);
        }
        else if (c == '(') op.push(c);
        else if (c == ')')
        {
            while (op.top() != '(') eval();
            op.pop();
        }
        else
        {
            while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
            op.push(c);
        }
    }
    while (op.size()) eval();
    cout << num.top() << endl;
    return 0;
}

我的代码

#include "iostream"
#include "stack"
#include "cstring"
#include "map"
using namespace std;
 
/**
 * 中缀表达式求值
 * 定义两个栈，stack1存储数字，stack2存储运算符，将字符串str元素一个个扫描，遇到数字型则进栈stack1，遇到运算符型，
 * 则要看看栈stack2栈顶元素运算符优先级是否比自己大或等于，如果真比自己大，那么那个运算符出栈，假设出栈是运算符a，
 * 那么此时从stack1中出栈两个数字b、c参与运算，把运算结果进栈stack1，此时此字符还不能进栈，如果栈顶优先级还比自己大或等于，
 * 那么那个栈顶运算符还要拿出来运算，直到有小于自己的自己才进栈；遇到‘（’直接进stack2，遇到’）’，则就要把这一对括号之间运算符都一个个拿出来运算
 * @return
 */
 
int cuclt(int x,int y,char c);
 
int main(){
    stack<int> s1;//数字栈
    stack<int> s2;//符号栈
 
    //定义符号位的优先级
    map<int,int> m;
    m['+'] = 1;
    m['-'] = 1;
    m['*'] = 2;
    m['/'] = 2;
    m['('] = 0;
 
    char bds[100];
    cin>>bds;
 
    int len = strlen(bds);
    int i = 0;
    while(i<len){
        if(bds[i]>='0' && bds[i]<='9'){//数字
            int num = 0;
            while (bds[i]>='0' && bds[i]<='9'){
                num = num * 10 + bds[i] -'0';
                i++;
            }
            s1.push(num);
        }else {//符号位
            //处理符号位
            if(bds[i]=='('){//符号位空，直接入栈,左括号，直接入栈
                s2.push(bds[i]);
            }else if(bds[i]==')') {//右括号，符号位要一直出栈，直到,第一个(出现
                while(s2.top()!='(') {
                    int czs = s2.top();s2.pop();
                    int x = s1.top();s1.pop();//出两个操作数
                    int y = s1.top();s1.pop();
 
                    s1.push(cuclt(y,x,czs));
                }
                s2.pop();//最后弹出左括号
            }else{
                    while(s2.size()>0 && m[s2.top()] >= m[bds[i]]){//栈中的优先级大于当前符号
                        //出栈
                        int czs = s2.top();s2.pop();
                        int x = s1.top();s1.pop();//出两个操作数
                        int y = s1.top();s1.pop();
                        s1.push(cuclt(y,x,czs));
                    }
                    s2.push(bds[i]);
            }
            i++;
        }
    }
 
    while (s2.size()){
        //出栈
        int czs = s2.top();s2.pop();
        int x = s1.top();s1.pop();//出两个操作数
        int y = s1.top();s1.pop();
        s1.push(cuclt(y,x,czs));
    }
 
    cout<<s1.top();
    return 0;
}
 
int cuclt(int x,int y,char c){
    int result = 0;
    if(c == '*'){
        result = x*y;
    }else if(c == '/'){
        result = x/y;
    }else if(c == '+'){
        result = x+y;
    }else if(c == '-'){
        result = x-y;
    }
    return result;
}

算法思想

定义两个栈：

数据栈：s1，用以存储数字；

运算符栈：s2，用以存储运算符；

将字符元素一个个扫描，遇到操作数则进栈s1，

遇到运算符型，需要判断：
s2栈顶元素运算符优先级是否比当前运算符大或等于：
1. 成立：
    1.1 那么s2栈顶运算符出栈：假设出栈是运算符a，那么此时从s1中出栈两个数字b、c参与运算，把运算结果进栈s1；
    1.2 循环1.1操作，直到栈顶元素不满足条件
    1.3 当前运算符入栈
2. 不成立：当前运算符入栈

遇到(直接进s1，
遇到)则就要把这一对括号之间运算符都一个个拿出来运算,与1.1处理过程一致