洛谷-P1449 后缀表达式 题解

题目链接：https://www.luogu.com.cn/problem/P1449

题目解析

什么是后缀表达式？

• 运算符写在两个操作数之后。
• 不需要括号，也不考虑运算符优先级。
• 计算顺序严格从左到右，遇到运算符就对最近的两个操作数进行运算。

例如：

• 中缀表达式：3 * (5 - 2) + 7
• 后缀表达式：3.5.2.-*7.+@

其中：

• . 表示一个操作数的结束
• @ 表示整个表达式的结束符号

核心思想

• 遍历字符串，逐字符处理。
• 遇到数字字符时，拼接成完整数字（直到遇到 .）。
• 遇到运算符（+ - * /）时，从栈中弹出两个操作数（注意顺序！）：先弹出的是右操作数后弹出的是左操作数
• 进行运算后，将结果压回栈中。
• 最终栈顶即为答案。

代码

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string s;
    cin >> s;
    stack<long long> nums;  // 用 long long 防止中间溢出
    string numStr = "";

    for (int i = 0; i < s.size(); i++) {
        char c = s[i];
        if (c >= '0' && c <= '9') {
            numStr += c;
        } else if (c == '.') {
            // 将当前数字字符串转为整数
            long long num = stoll(numStr);
            nums.push(num);
            numStr = "";
        } else if (c == '@') {
            // 结束符，不做操作
            break;
        } else {
            // 运算符：+ - * /
            long long b = nums.top(); nums.pop();
            long long a = nums.top(); nums.pop();
            long long res;
            switch (c) {
                case '+': res = a + b; break;
                case '-': res = a - b; break;
                case '*': res = a * b; break;
                case '/': res = a / b; break; // C++ 整数除法已向 0 取整
            }
            nums.push(res);
        }
    }

    cout << nums.top() << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(|s|)，每个字符访问一次。
• 空间复杂度：O(n)，栈中最多存储所有操作数（约 |s|/2）。