P1449 后缀表达式——题解

思路

使用一个整数栈：

1. 连续读到数字时，把它们组合成一个多位整数 num；
2. 遇到 .，说明一个操作数结束，把 num 入栈并清零；
3. 遇到运算符，从栈顶依次弹出右操作数 b 和左操作数 a，计算 a 运算符 b，再把结果压回栈；
4. 遇到 @ 停止，栈顶就是答案。

减法和除法必须注意操作数顺序：先弹出的是右操作数。

复杂度

时间复杂度 $O(|s|)$，空间复杂度 $O(|s|)$。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    long long st[100];
    int top = 0;
    long long num = 0;

    for (char c : s) {
        if (c >= '0' && c <= '9') {
            num = num * 10 + c - '0';
        } else if (c == '.') {
            st[++top] = num;
            num = 0;
        } else if (c == '@') {
            break;
        } else {
            long long b = st[top--];
            long long a = st[top--];
            if (c == '+') st[++top] = a + b;
            if (c == '-') st[++top] = a - b;
            if (c == '*') st[++top] = a * b;
            if (c == '/') st[++top] = a / b;
        }
    }
    cout << st[top] << '\n';
    return 0;
}

#include <bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; long long st[100]; int top=0; long long num=0; for(char c:s){ if(c>='0'&&c<='9') num=num10+c-'0'; else if(c=='.'){ st[++top]=num; num=0; } else if(c=='@') break; else{ long long b=st[top--],a=st[top--]; if(c=='+') st[++top]=a+b; else if(c=='-') st[++top]=a-b; else if(c=='') st[++top]=a*b; else st[++top]=a/b; } } cout<<st[top]<<'\n'; return 0; }