计算只含加减乘除的中缀表达式

当时第一次写表达式求值，脑子里一团乱，后来照着”中缀转后缀 + 后缀求值”这两步才理清。核心思路是先靠运算符栈把中缀换成后缀，再拿一个栈算后缀，这篇把步骤记下来。

思路

整个问题拆成两块：先中缀转后缀，再算后缀表达式，两头都得用栈。

中缀表达式转后缀表达式

1. inex:中缀表达式，postex:后缀表达式，stk运算符栈
2. 遍历inex
3. 如果为运算数，则直接添加到postex中
4. 如果为(，则直接入栈stk
5. 如果为)，一直取出栈顶元素（运算符），直到栈顶运算符为(为止，取出(，不将)入栈
6. 如果为+、-、*、/运算符，规定为两种优先级。只有目前操作运算符优先级高于栈顶运算符优先级（或者栈空）时才能直接入栈，小于或等于栈顶优先级（注意栈空是直接入栈，所以先处理前者更为简便）需要一直出栈，直至满足当前运算符优先级大于栈顶运算符优先级（或者栈已空），将运算符入栈。出栈的运算符直接添加到postex中
7. 将栈中剩余的运算符依次添加到postex中。这样得到的postex就是后缀表达式。

后缀表达式的计算

1. 遍历postex
2. 如果是运算数，则直接入栈
3. 如果是运算符，则依次取出两个栈顶元素 a、b，将运算结果 (b \times a) 入栈
4. 循环结束，栈中只剩余一个数，该数就是中缀表达式的运算结果

示例代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long
//#define int ll
#define pii pair<int, int>
#define all(x) x.begin(),x.end()
#define fer(i, m, n) for(int i = m; i < n; ++i)
#define ferd(i, m, n) for(int i = m; i >= n; --i)
#define dbg(x) cout << #x << ' ' << char(61) << ' ' << x << '\n'

const int MOD = 1e9 + 7;
const int N = 2e5 + 2;
const int inf = 1e9;

// 中缀表达式转后缀表达式
void InexToPostex(string inex, string& postex) {
    stack<char> stk;

    map<char, int> mp = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    for(char c : inex) {
        if(c >= '0' && c <= '9') postex += c;
        else if(c == '(') stk.push(c);
        else if(c == ')') {
            while(!stk.empty() && stk.top() != '(')
                postex += stk.top(), stk.pop();
            stk.pop();
        }
        else if(stk.empty() || mp[c] > mp[stk.top()]) stk.push(c);
        else if(mp[c] <= mp[stk.top()]) {
            while(!stk.empty() && mp[c] <= mp[stk.top()])
                postex += stk.top(), stk.pop();
            stk.push(c);
        }
    }
    while(!stk.empty()) postex += stk.top(), stk.pop();

    cout << "postex: " << '\n';
    for(char c : postex) cout << c << ' ';
    cout << '\n';
}

// 后缀表达式计算
void cal(string postex) {
    stack<int> stk;
    for(char c : postex) {
        if(c >= '0' && c <= '9') stk.push(c - '0');
        else{
            int a = stk.top(); stk.pop();
            int b = stk.top(); stk.pop();
            if(c == '+') stk.push(a + b);
            else if(c == '-') stk.push(b - a);
            else if(c == '*') stk.push(a * b);
            else if(c == '/') stk.push(b / a);
        }
    }
    cout << "ans: " << stk.top() << '\n';
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    string inex, postex;
    cin >> inex;
    InexToPostex(inex, postex);
    cal(postex);

    return 0;
}

样例输入输出

输入

2*(3+5)+7/1-4

输出

postex:
2 3 5 + * 7 1 / + 4 -
ans: 19

题目

P1449 后缀表达式

思路

我是把每个字符扫一遍：数字先攒着，碰到 . 就把攒好的数压进栈，碰到运算符就弹两个数算一下，最后栈顶就是答案。

示例代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long
//#define int ll
#define pii pair<int, int>
#define all(x) x.begin(),x.end()
#define fer(i, m, n) for(int i = m; i < n; ++i)
#define ferd(i, m, n) for(int i = m; i >= n; --i)
#define dbg(x) cerr << #x << ' ' << char(61) << ' ' << x << '\n'

const int MOD = 1e9 + 7;
const int N = 2e5 + 2;
const int inf = 1e9;

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    string ex;
    cin >> ex;
    stack<int> stk;

    string s;
    for(char c : ex) {
    	if(c >= '0' && c <= '9') s += c;
    	else if(c == '.') {
    		stk.push(stoi(s));
    		s.clear();
    	}
    	else if(c == '@') break;
    	else{
    		int a = stk.top(); stk.pop();
    		int b = stk.top(); stk.pop();
    		if(c == '+') stk.push(b + a);
    		else if(c == '-') stk.push(b - a);
    		else if(c == '*') stk.push(b * a);
    		else if(c == '/') stk.push(b / a);
    	}
    }
    cout << stk.top() << '\n';
    return 0;
}