150、逆波兰表达式求值（栈与队列）(Leetcode刷题笔记)
欢迎大家访问我的GitHub博客
https://lunan0320.cn 文章目录
150、逆波兰表达式求值（栈与队列）(Leetcode刷题笔记)
题目解题代码 C++(核心代码)解题代码（本地编译运行）算法效率 题目
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入：tokens = [“2”,“1”,"+",“3”,"*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = [“4”,“13”,“5”,"/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13/ 5)) = 6
示例 3：
输入：tokens = [“10”,“6”,“9”,“3”,"+","-11","","/","",“17”,"+",“5”,"+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
解题代码 C++(核心代码)
解题思路：其实这无非就是个中缀表达式的过程，用栈很好实现。 需要注意的是，c++中switch-case结构不能用字符串。
而且，弹出元素的时候，需要考虑顺序。
class Solution {public: int evalRPN(vector& tokens) { stack st;for (int i = 0; i < tokens.size(); i++) {//先判断是否是特殊符号if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {//从栈中弹出两个字符 //此处一定要注意顺序，num2和num1的顺序int num2 = st.top();st.pop();int num1 = st.top();st.pop();//对于特殊字符 特殊处理if (tokens[i] == "+") st.push(num1 + num2);else if (tokens[i] == "-") st.push(num1 - num2);else if (tokens[i] == "*") st.push(num1*num2);else st.push(num1 / num2);//switch (c) {//case '+'://st.push(num1 + num2);//break;//case "-"://st.push(num1 - num2);//break;//case "*"://st.push(num1*num2);//break;//case "/"://st.push(num1 / num2);//break;//}}else { //如果不是操作符，那么就入栈即可。 //此处需要注意 要把字符串转换为整型， 用stoi()函数即可st.push(stoi(tokens[i])); }}//弹出栈顶元素即是结果int res = st.top();return res; }};
解题代码（本地编译运行）
#include #include #include #include using namespace std;#include "head.h"//逆波兰表达式求值class Solution {public:int evalRPN(vector& tokens) {stack st;for (int i = 0; i < tokens.size(); i++) {//先判断是否是特殊符号if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {//从栈中弹出两个字符//此处一定要注意顺序，num2和num1的顺序int num2 = st.top();st.pop();int num1 = st.top();st.pop();//对于特殊字符 特殊处理if (tokens[i] == "+") st.push(num1 + num2);else if (tokens[i] == "-") st.push(num1 - num2);else if (tokens[i] == "*") st.push(num1*num2);else st.push(num1 / num2);//switch (c) {//case '+'://st.push(num1 + num2);//break;//case "-"://st.push(num1 - num2);//break;//case "*"://st.push(num1*num2);//break;//case "/"://st.push(num1 / num2);//break;//}}else { //如果不是操作符，那么就入栈即可。 //此处需要注意 要把字符串转换为整型， 用stoi()函数即可st.push(stoi(tokens[i])); }}//弹出栈顶元素即是结果int res = st.top();return res;}};#include "myStack.h"// 逆波兰表达式求值int main() {vector tokens{ "4","13","5","/","+"};Solution solution;cout << solution.evalRPN(tokens) << endl;return 0;}
算法效率
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：11.6 MB, 在所有 C++ 提交中击败了84.68%的用户