✨个人主页： 北 海
?所属专栏： C/C++相关题解
?每篇一句： 图片来源
文章目录
?前言?️正文1、什么是逆波兰表达式？2、150. 逆波兰表达式求值 ⭐⭐3、224. 基本计算器 ⭐⭐⭐ ?总结
?前言
好久没有更新题解系列博客了，今天要学习的是 逆波兰表达式，作为计算机中的重要概念，值得花时间去学习，并且其中还必须使用 容器适配器，非常适合用来练手
?️正文
1、什么是逆波兰表达式？
逆波兰表达式 又称为 后缀表达式，我们从小到大学习的数学相关运算式都是 前缀表达式
前缀表达式：运算符在操作数中间(a + b) * c后缀表达式：运算符在操作数后面 a b + c * 为什么会存在这种反人类的表达式呢？
因为运算式中，可能存在( ) 提高运算优先级的现象，计算机不像人类一样，可以一眼找到 ( ) 进行运算，只能通过特殊方法，处理运算式，使其能进行正常运算 因此，后缀表达式中是没有括号的
操作数：a、b、c
运算符：+、*
后缀表达式 的计算步骤：
从左往右，扫描表达式获取操作数1 与 操作数2再获取 运算符进行运算：操作数1 运算符 操作数2，获取运算结果将运算结果继续与后续 操作数、运算符 进行计算 比如计算 12+3*
1 + 2 = 3其次再计算 3 * 3 = 9 最后的 9 就是最终运算结果，逆波兰表达式（后缀表达式）有效解决了计算时的优先级问题
了解 逆波兰表达式 基础知识后，就可以尝试解决相关问题了~
2、150. 逆波兰表达式求值 ⭐⭐
首先来看看第一题，也是比较简单的一题：150.逆波兰表达式求值
题目链接：150.逆波兰表达式求值
题目要求：根据 逆波兰表达式 计算出结果
这里可以直接根据 逆波兰表达式（后缀表达式） 的计算步骤进行解题
解题思路：
从左往右扫描表达式（遍历即可）遇到操作数（数字），入栈遇到运算符，取出栈中的两个两个操作数，进行计算将计算结果重新入栈如此重复，直到表达式被扫描完毕所需要的辅助工具：栈 stack
复杂度分析：
O(N) 遍历一遍表达式 + 出栈入栈空间复杂度 O(N) 需要使用大小足够的栈 
转化为代码是这样的：
class Solution {public: int evalRPN(vector<string>& tokens) { //首先需要一个栈，用来存储操作数 stack<int> numStack; //对表达式进行遍历 for (size_t pos = 0; pos != tokens.size(); pos++) { //判断是否为操作数 //需要注意负数,负数大小是大于1的 if (isdigit(tokens[pos][0]) || tokens[pos].size() > 1) { //满足条件，入栈 //注意：入栈的是整型！ numStack.push(stoi(tokens[pos])); } else { //此时为运算符，需要进行运算 //注意：先取的是右操作数 int rightNum = numStack.top(); numStack.pop(); int leftNum = numStack.top(); numStack.pop(); char oper = tokens[pos][0]; //运算符 int val = 0; //运算结果 switch (oper) { case '+': val = leftNum + rightNum; break; case '-': val = leftNum - rightNum; break; case '*': val = leftNum * rightNum; break; case '/': val = leftNum / rightNum; break; default: break; } //将运算结果入栈 numStack.push(val); } } //此时栈中的元素，就是计算结果 return numStack.top(); }};运行结果：
需要注意的点：
isdigit 函数可以判断字符是否数字字符判断是否为操作数时，需要注意负数的情况，如 -100，可以通过判断字符串大小解决（运算符大小只为1）操作数入栈时，入的是整型，而非字符串，可以使用 stoi 函数进行转换取操作数时，先取到的是右操作数，-、/ 这两个运算符需要注意运算顺序获得运算结果后，需要再次入栈 3、224. 基本计算器 ⭐⭐⭐
直接利用 后缀表达式 计算出结果很简单，但将 中缀表达式 转为 后缀表达式 就比较麻烦了
在力扣中就存在这样一道 困难题
题目链接：基本计算器
题目要求：根据 中缀表达式，计算出结果
注意： 给出的 中缀表达式 中只涉及 +、- 运算，但是其中又会存在很多特殊情况
为了使得这些特殊情况统一化，在进行表达式转换前，需要先去除其中的空格，这样就能以较为统一的视角解决问题
解题思路：
去除中缀表达式 中的空格，方便后续进行转换获取 逆波兰表达式（后缀表达式） （重难点）根据 逆波兰表达式 求出结果即可 如何将 中缀表达式 转换为 后缀表达式 ?
vector 中）运算符：如果栈为空，直接入栈；如果栈不为空，与栈顶运算符进行优先级比较，如果比栈顶运算符优先级高，入栈，否则将栈顶运算符弹出（输出），继续比较对于 ()，认为它们的优先级都为最低，并且 ( 直接入栈，而 ) 直接弹出栈顶元素，直到遇见 (最后将栈中的运算符全部弹出 
注意： 对于可能存在的负数，需要进行特别处理
当- 单独出现时（左右都没有操作数），表示此时需要将右边括号中的计算结果 * -1，此时可以直接先输出元素 0，后续进行 0 - val 时，可以满足需求当 - 仅有右边有操作数时，此时为一个单独出现的负数，输出此负数即可当 - 左右都有操作数时，此时的 - 就是一个单纯的运算符 class Solution {public: //去除空格 int spaceRemove(string& s) { int begin = 0; int end = 0; int alphaNum = 0; while (end != s.size()) { if (s[end] != ' ') { if (s[end] != '(' && s[end] != ')') alphaNum++; s[begin] = s[end]; begin++; end++; } else end++; } s.resize(begin); return alphaNum; } //判断是否为负数 bool isNega(const string& s, int i) { //合法的负数：左边为 '(' 或者 左边为空 return s[i] == '-' && (i == 0 || s[i - 1] == '('); } //获取逆波兰表达式 void getAntiPoland(vector<string>& tokens, string s) { //借助栈，存储运算符 stack<char> oper; size_t i = 0; while (i < s.size()) { string str; //操作数直接输出 if (isdigit(s[i]) || isNega(s, i)) { //有可能为负数 if (s[i] == '-') { //特殊情况，'-' 单独出现，不配合数字 if (i + 1 < s.size() && !isdigit(s[i + 1])) { str += '0'; oper.push(s[i++]); } //普通负数的情况 else { str += s[i]; i++; } } //处理多位数的情况 while (isdigit(s[i])) { str += s[i]; i++; } } else { //此时为运算符 //栈空 或者 '(' 直接入栈 if (oper.empty() || s[i] == '(') oper.push(s[i]); else { if (s[i] == ')') { //此时需要不断弹出 char tmp = oper.top(); oper.pop(); while (tmp != '(') { str += tmp; tmp = oper.top(); oper.pop(); } } else if (oper.top() != '(') { //此时弹出并入栈 str = oper.top(); oper.pop(); oper.push(s[i]); } else { //此时该运算符的优先级比前面的高，直接入栈 oper.push(s[i]); } } i++; } if (!str.empty()) tokens.push_back(str); //计入中缀表达式 } //最后需要将栈中的运算符全部弹出 string str; while (!oper.empty()) { str += oper.top(); oper.pop(); } if (!str.empty()) tokens.push_back(str); } int evalRPN(vector<string>& tokens) { //首先需要一个栈，用来存储操作数 stack<int> numStack; //对表达式进行遍历 for (size_t pos = 0; pos != tokens.size(); pos++) { //判断是否为操作数 //需要注意负数,负数大小是大于1的 if (isdigit(tokens[pos][0]) || tokens[pos].size() > 1) { //满足条件，入栈 //注意：入栈的是整型！ numStack.push(stoi(tokens[pos])); } else { //此时为运算符，需要进行运算 //注意：先取的是右操作数 int rightNum = numStack.top(); numStack.pop(); int leftNum = numStack.top(); numStack.pop(); char oper = tokens[pos][0]; //运算符 int val = 0; //运算结果 switch (oper) { case '+': val = leftNum + rightNum; break; case '-': val = leftNum - rightNum; break; default: break; } //将运算结果入栈 numStack.push(val); } } //此时栈中的元素，就是计算结果 return numStack.top(); } int calculate(string s) { //核心：运算符入栈，操作数输出，根据运算符优先级进行弹出 int alphaNum = spaceRemove(s); //为了方便后续操作，可以先去除空格 vector<string> tokens; //存储操作数+运算符的后缀表达式 tokens.reserve(alphaNum);//提前扩容，避免造成浪费 getAntiPoland(tokens, s); //获取逆波兰表达式（后缀表达式） int val = evalRPN(tokens); //复用之前写的代码 return val; }};
注：因为走的是先转换，再计算的步骤，所以整体性能会比较差，但其中加入了 逆波兰表达式 的相关知识，还是比较适合用来练手的
?总结
以上就是本次 逆波兰表达式 相关内容了，希望你在看完本文后能够有所收获
如果你觉得本文写的还不错的话，可以留下一个小小的赞?，你的支持是我分享的最大动力！
如果本文有不足或错误的地方，随时欢迎指出，我会在第一时间改正
相关文章推荐
C语言题解 | 去重数组&&合并数组
C语言题解 | 消失的数字&轮转数组
C语言题解——除自身以外数组的乘积（力扣 第238题）
剑指Offer 第53题：数字在升序数组中出现的次数
C语言题解——倒置字符串（剑指Offer 第58题）
