✨个人主页: 北 海
所属专栏: C/C++相关题解
每篇一句: 图片来源

  • A year from now you may wish you had started today.
    • 明年今日,你会希望此时此刻的自己已经开始行动了。


文章目录

  • 前言
  • ️正文
    • 1、什么是逆波兰表达式?
    • 2、150. 逆波兰表达式求值 ⭐⭐
    • 3、224. 基本计算器 ⭐⭐⭐
  • 总结

前言

好久没有更新题解系列博客了,今天要学习的是 逆波兰表达式,作为计算机中的重要概念,值得花时间去学习,并且其中还必须使用 容器适配器,非常适合用来练手


️正文

1、什么是逆波兰表达式?

逆波兰表达式 又称为 后缀表达式,我们从小到大学习的数学相关运算式都是 前缀表达式

  • 前缀表达式:运算符在操作数中间 (a + b) * c
  • 后缀表达式:运算符在操作数后面 a b + c *

为什么会存在这种反人类的表达式呢?

  • 因为运算式中,可能存在 ( ) 提高运算优先级的现象,计算机不像人类一样,可以一眼找到 ( ) 进行运算,只能通过特殊方法,处理运算式,使其能进行正常运算

因此,后缀表达式中是没有括号的

操作数:a、b、c
运算符:+、*

后缀表达式 的计算步骤:

  1. 从左往右,扫描表达式
  2. 获取 操作数1操作数2
  3. 再获取 运算符
  4. 进行运算:操作数1 运算符 操作数2,获取运算结果
  5. 将运算结果继续与后续 操作数运算符 进行计算

比如计算 12+3*

  • 首先计算 1 + 2 = 3
  • 其次再计算 3 * 3 = 9

最后的 9 就是最终运算结果,逆波兰表达式(后缀表达式)有效解决了计算时的优先级问题

了解 逆波兰表达式 基础知识后,就可以尝试解决相关问题了~


2、150. 逆波兰表达式求值 ⭐⭐

首先来看看第一题,也是比较简单的一题:150.逆波兰表达式求值

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

题目要求:根据 逆波兰表达式 计算出结果

这里可以直接根据 逆波兰表达式(后缀表达式) 的计算步骤进行解题

解题思路:

  1. 从左往右扫描表达式(遍历即可)
  2. 遇到操作数(数字),入栈
  3. 遇到运算符,取出栈中的两个两个操作数,进行计算
  4. 将计算结果重新入栈
  5. 如此重复,直到表达式被扫描完毕

所需要的辅助工具: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. 基本计算器 ⭐⭐⭐

直接利用 后缀表达式 计算出结果很简单,但将 中缀表达式 转为 后缀表达式 就比较麻烦了

在力扣中就存在这样一道 困难题

题目链接:基本计算器


题目要求:根据 中缀表达式,计算出结果

注意: 给出的 中缀表达式 中只涉及 +- 运算,但是其中又会存在很多特殊情况


为了使得这些特殊情况统一化,在进行表达式转换前,需要先去除其中的空格,这样就能以较为统一的视角解决问题

解题思路:

  1. 去除 中缀表达式 中的空格,方便后续进行转换
  2. 获取 逆波兰表达式(后缀表达式) (重难点)
  3. 根据 逆波兰表达式 求出结果即可

如何将 中缀表达式 转换为 后缀表达式 ” />

注意: 对于可能存在的负数,需要进行特别处理

  • - 单独出现时(左右都没有操作数),表示此时需要将右边括号中的计算结果 * -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++;}elseend++;}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题)