解题思路

逆波兰表达式（后缀表达式）是一种不需要括号就能明确表示运算优先级的数学表达式表示方法。解题的核心思路是使用栈数据结构来模拟计算过程。

算法流程：

1. 创建一个空栈用于存储操作数
2. 将输入字符串按逗号分割为元素列表
3. 遍历每个元素：
   • 如果是数字，直接压入栈中
   • 如果是运算符，从栈中弹出两个操作数（注意顺序：先弹出的是右操作数，后弹出的是左操作数）
   • 根据运算符进行相应计算，将结果压回栈中
4. 遍历结束后，栈中唯一的元素就是最终结果

对于除法运算，需要注意整数除法只保留整数部分，并且要注意运算顺序（先弹出的操作数是右操作数）。

复杂度分析

• 时间复杂度：O(n)，其中n是逆波兰表达式中元素的个数。每个元素只需处理一次。
• 空间复杂度：O(n)，最坏情况下栈的大小约为n/2（当所有操作数连续出现时）。

代码实现

Python

from typing import List

def evalRPN(tokens: List[str]) -> int:
    stack = []
    for token in tokens:
        if token in '+-*/':
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                # 整数除法，向零取整
                stack.append(int(a / b))
        else:
            stack.append(int(token))
    return stack[0]

def main():
    # 读取输入并按逗号分割
    s = input().strip()
    # 使用安全的方式解析字符串为列表
    tokens = [x.strip() for x in s.split(',')]
    result = evalRPN(tokens)
    print(result)

if __name__ == '__main__':
    main()

Java

import java.util.*;

public class Main {
    public static int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String token : tokens) {
            if ("+-*/".contains(token)) {
                int b = stack.pop();
                int a = stack.pop();
                switch (token) {
                    case "+":
                        stack.push(a + b);
                        break;
                    case "-":
                        stack.push(a - b);
                        break;
                    case "*":
                        stack.push(a * b);
                        break;
                    case "/":
                        stack.push(a / b); // 整数除法自动向零取整
                        break;
                }
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        // 按逗号分割输入字符串
        String[] tokens = input.split(",");
        int result = evalRPN(tokens);
        System.out.println(result);
        scanner.close();
    }
}

C++

#include <iostream>
#include <stack>
#include <string>
#include <sstream>
#include <vector>

using namespace std;

int evalRPN(vector<string>& tokens) {
    stack<int> st;
    for (const auto& token : tokens) {
        if (token == "+" || token == "-" || token == "*" || token == "/") {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            if (token == "+") st.push(a + b);
            else if (token == "-") st.push(a - b);
            else if (token == "*") st.push(a * b);
            else if (token == "/") st.push(a / b); // 整数除法自动向零取整
        } else {
            st.push(stoi(token));
        }
    }
    return st.top();
}

int main() {
    string input;
    getline(cin, input);
    
    // 按逗号分割输入字符串
    vector<string> tokens;
    stringstream ss(input);
    string token;
    while (getline(ss, token, ',')) {
        tokens.push_back(token);
    }
    
    int result = evalRPN(tokens);
    cout << result << endl;
    
    return 0;
}

题目内容

逆波兰表达式可以在避免使用括号的情况下，完成表达式的有优先级的运算。

逆波兰表达式由操作数 $(operand)$ 和运算符 $(operator)$ 构成，不使用括号，即可表示带优先级的运算关系。

例如:$2,1,+,3,*$

该算式转化为常见的中缀算术表达式为:$((2+1)*3)=9$

一般在计算机中，使用栈操作进行逆波兰表达式的计算。

遇到操作数就入栈，遇到运算符，就对当前栈顶元素进行相应的一元或者二元运算。

具体求解过程如下:

1.声明一个操作数栈用来存放操作数，按顺序遍历逆波兰表达式的字符;

2.如果当前字符是操作数，则直接入栈;

3.如果当前字符是操作符，则从栈中取出 $2$ 个操作数，并按照当前操作符进行计算，将计算结果重新入栈。

4.最后，返回操作数栈中唯一的一个值，即为逆波兰表达式的求值结果。

说明:

1.有效的算符包括 $+、-、*、/$ 。

2.整数除法只保留整数部分。

3.给定逆波兰表达式总是有效的。

输入描述

输入一行，包含有效的逆波兰表达式，每个元素之间使用逗号 $(,)$ 分隔，简化表达式解析。

数字元素范围 $0<=num<=100$ 。

符号元素包括 $+、-、*、/$ 。

输出描述

输出一行，包含逆波兰表达式计算结果。

样例1

输入

2,1,+,3,*

输出

9

样例2

输入

4,13,5,/,+

输出

6