当前位置：首页 > news >正文

【Leetcode每日一题】综合练习 - 逆波兰表达式求值（难度⭐⭐）（73）

news 2025/7/28 2:55:01

1. 题目解析

题目链接：150. 逆波兰表达式求值

这个问题的理解其实相当简单，只需看一下示例，基本就能明白其含义了。

2.算法原理

数据结构选择：
- 使用栈（stack<int>）来存储操作数，以便进行后进先出（LIFO）的操作。
- 使用哈希映射（map<string, function<int(int, int)>>）来存储操作符及其对应的操作函数。
操作符函数映射：
- 通过map容器建立操作符到操作函数的映射，使得在遍历表达式时能够快速找到对应的操作符函数。
遍历表达式：
- 遍历输入的逆波兰表达式（RPN）中的每一个标记（tokens）。
操作符处理：
- 如果当前标记是操作符，则从栈中弹出两个操作数（右操作数在前，左操作数在后）。
- 使用哈希映射中对应的操作函数对这两个操作数进行计算，并将结果压回栈中。
操作数处理：
- 如果当前标记是操作数，则将其转换为整数（stoi(s)）并压入栈中。
结果返回：
- 遍历结束后，栈中只剩下一个元素，即逆波兰表达式的计算结果，返回该元素作为函数结果。
注意事项：
- 本算法假设输入的逆波兰表达式是有效的，即不包含无效的操作符、操作数以及除法运算中的零除错误。
- 逆波兰表达式的特点是操作符在操作数之后，因此不需要考虑操作符的优先级问题。

3.代码编写

class Solution 
{
public:int evalRPN(vector<string>& tokens) {stack<int> st;map<string, function<int(int, int)>> opfunc{{"+", [](int x, int y){return x + y;}},{"-", [](int x, int y){return x - y;}},{"*", [](int x, int y){return x * y;}},{"/", [](int x, int y){return x / y;}}};for(auto& s : tokens){if(opfunc.find(s) != opfunc.end()){int r = st.top();st.pop();int l = st.top();st.pop();st.push(opfunc[s](l, r));}else{st.push(stoi(s));}}return st.top();}
};