P76058 后缀表达式计算 — 题解

专题： STL
适用题目： 新生 OJ 本地题包中的 P76058，不要直接用于外站同名题。

解题思路

空格分割表达式：数字入栈，遇到运算符就先取出右操作数、再取左操作数，计算后压回。

复杂度

时间 $O(L)$，空间 $O(L)$。

易错点

减法、除法有顺序：计算的是 a-b 或 a/b。

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    getline(cin,s);
    stringstream in(s);
    stack<ll>st;
    string token;
    while(in>>token){
        if(token.size()==1&&string("+-*/").find(token[0])!=string::npos){
            ll b=st.top();
            st.pop();
            ll a=st.top();
            st.pop();
            ll v=0;
            if(token=="+")v=a+b;
            else if(token=="-")v=a-b;
            else if(token=="*")v=a*b;
            else v=a/b;
            st.push(v);
        }
        else st.push(stoll(token));
    }
    cout<<st.top()<<nl;
    return 0;
}

为什么只提供 C++： 本题专题要求使用 STL 容器或算法，C 语言没有 STL；C 可以用手写数据结构解决，但不属于本专题的教学目标。

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。