中缀表达式求值

对于表达式求值，我们通常用栈来操作。常用的做法是先转换为后缀表达式，再利用栈来求值。步骤如下：

开一个栈一个储存运算符，再开一个结构存后缀表达式，可以选择string数组
每遇到一个数字，将其加入到后缀表达式种
遇到左括号，加入到符号栈种
遇到右括号，不断将栈顶元素添加到后缀表达式中，直到遇到左括号，然后弹出左括号
遇到普通运算符，只要栈顶符号的优先级不低于新符号，就不断取出栈顶元素存到后缀表达式，然后将新符号入栈，优先级顺序为乘除>加减>左括号
依次取出符号栈中剩余元素，加入到后缀表达式中
将得到的后缀表达式求值

Note

代码在取栈顶元素时容易出错，需要注意对栈为空时的判断

Code

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135


#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define mem(a,b) memset(a,b,sizeof(a))
#define debug cout<<0<<endl
#define ll long long
const int MAXN = 1e4 + 10;
const int MOD = 1e9 + 7;
using namespace std;

stack<int> stnumber;
stack<char> stsign;
stack<int> ans;

struct node {
    string s="";
} a[MAXN];

int oder(char c) {
    if (c == '+' || c == '-') return 1;
    else if (c == '*' || c == '/') return 2;
    return 0;
}

int toInt(string ss) {
    int res = 0;
    for (int i = 0; i < ss.length(); i++) {
        res = res*10 + ss[i] - '0';
    }
    return res;
}

int calc(int aa, int bb, char op) {
    switch (op) {
        case '+':
            return aa + bb;
            break;
        case '/': 
            return bb / aa;
            break;
        case '*':
            return aa*bb;
            break;
        case '-': 
            return bb - aa;
            break;
        default:
            break;
    }
}

bool isnum(char si) {
    if (si <= '9' && si >= '0') return true;
    return false;
}

int cur = 0;



int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    string s;
    cin >> s;
    N = s.length();
    int len = 0;
    for (int i = 0; i < N; i += len) {
        len = 0;
        if (isnum(s[i])) {
            string t = "";
            for (int j = i; j < N; j++) {
                if (isnum(s[j])) {
                    t += s[j];
                    len++;
                } else {
                    break;
                }
            }
            a[++cur].s = t;
        } else {
            if (s[i] == '(') 
                stsign.push(s[i]);
            else if (s[i] == ')') {
                while (stsign.top() != '(') {
                    char op = stsign.top();
                    stsign.pop();
                    a[++cur].s += op;
                }
                stsign.pop();
            } else {
                char op = s[i];
                if (!stsign.empty())
                while (!stsign.empty() && oder(stsign.top()) >= oder(op)) {
                    a[++cur].s += stsign.top();
                    stsign.pop();
                    //if (stsign.empty()) break;
                }
                stsign.push(op);
            }
            len = 1;
        }
    }
    while (!stsign.empty()) {
        char op = stsign.top();
        stsign.pop();
        a[++cur].s += op;
    }
    // for (int i = 1; i <= cur; i++) {
    //     cout << a[i].s << endl;
    // }
    for (int i = 1; i <= cur; i++) {
        int temp;
        if (isnum(a[i].s[0])) {
            temp = toInt(a[i].s);
            ans.push(temp);
        } else {
            int aa = ans.top(); ans.pop();
            int bb = ans.top(); ans.pop();
            ans.push(calc(aa, bb, a[i].s[0]));
        }

    }
    cout << ans.top();
    return 0;
}