本文主要是介绍LeetCode - 150. 逆波兰表达式求值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
LeetCode - 150. 逆波兰表达式求值
解题思路：
想要解决该题目，我们首先需要知道什么是逆波兰表达式，逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
- 我们平常使用的算式则是一种中缀表达式，如( 1 + 2 )× ( 3 + 4 ) 。
- 该算式的逆波兰表达式写法为( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：
- 去掉括号后表达式无歧义，上式即便写成1 2 + 3 4 + * 也可以依据次序计算出正确结果。
- 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。
动画思路：
解题代码：
class Solution {
public:// 评估逆波兰表达式的主函数int evalRPN(vector<string>& tokens) {stack<int> st; // 使用整数栈来存储中间计算结果// 遍历所有的token（即每一个数字或运算符）for (size_t i = 0; i < tokens.size(); i++) {int left, right; // 用于存储两个操作数// 根据当前token的内容决定操作if (tokens[i] == "+") { // 加法运算符GetNum(st, left, right); // 从栈中取两个数st.push(left + right); // 将两数之和压入栈中} else if (tokens[i] == "-") { // 减法运算符GetNum(st, left, right); // 从栈中取两个数st.push(left - right); // 将两数之差压入栈中} else if (tokens[i] == "*") { // 乘法运算符GetNum(st, left, right); // 从栈中取两个数st.push(left * right); // 将两数之积压入栈中} else if (tokens[i] == "/") { // 除法运算符GetNum(st, left, right); // 从栈中取两个数st.push(left / right); // 将两数之商压入栈中} else { // 数字st.push(stoi(tokens[i])); // 将字符串转换为整数并压入栈中}}return st.top(); // 返回栈顶元素，即为表达式的最终结果}// 从栈中取出两个操作数的辅助函数void GetNum(stack<int>& st, int& left, int& right) {right = st.top(); // 栈顶是右操作数st.pop(); // 弹出栈顶元素left = st.top(); // 下一个栈顶是左操作数st.pop(); // 弹出栈顶元素}
};
这篇关于LeetCode - 150. 逆波兰表达式求值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
