✨个人主页: 北 海
🎉所属专栏: C/C++相关题解
🎊每篇一句: 图片来源
- A year from now you may wish you had started today.
- 明年今日,你会希望此时此刻的自己已经开始行动了。
🌇前言
好久没有更新题解系列博客了,今天要学习的是 逆波兰表达式
,作为计算机中的重要概念,值得花时间去学习,并且其中还必须使用 容器适配器
,非常适合用来练手
🏙️正文
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
函数进行转换 - 取操作数时,先取到的是右操作数,
-
、/
这两个运算符需要注意运算顺序 - 获得运算结果后,需要再次入栈
2023.6.4 更新
//2023.6.4 更新
//利用包装器和lambda,使代码更加优雅
#include <map>
#include <functional>
class Solution {
public:
int evalRPN(vector<string>& tokens) {
//首先需要一个栈,用来存储操作数
stack<int> numStack;
map<string, function<int(int,int)>> table =
{
{"+", [](int leftNum, int rightNum)->int{ return leftNum + rightNum;} },
{"-", [](int leftNum, int rightNum)->int{ return leftNum - rightNum;} },
{"*", [](int leftNum, int rightNum)->int{ return leftNum * rightNum;} },
{"/", [](int leftNum, int rightNum)->int{ return leftNum / rightNum;} }
};
//对表达式进行遍历
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();
string oper = tokens[pos]; //运算符
int val = table[oper](leftNum, rightNum); //运算结果
//将运算结果入栈
numStack.push(val);
}
}
//此时栈中的元素,就是计算结果
return numStack.top();
}
};
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;
}
};
注:因为走的是先转换
,再计算
的步骤,所以整体性能会比较差,但其中加入了 逆波兰表达式
的相关知识,还是比较适合用来练手的
🌆总结
以上就是本次 逆波兰表达式
相关内容了,希望你在看完本文后能够有所收获
如果你觉得本文写的还不错的话,可以留下一个小小的赞👍,你的支持是我分享的最大动力!
如果本文有不足或错误的地方,随时欢迎指出,我会在第一时间改正
文章来源地址https://www.toymoban.com/news/detail-430576.html
相关文章推荐 文章来源:https://www.toymoban.com/news/detail-430576.html
C语言题解 | 去重数组&&合并数组
C语言题解 | 消失的数字&轮转数组
C语言题解——除自身以外数组的乘积(力扣 第238题)
剑指Offer 第53题:数字在升序数组中出现的次数
C语言题解——倒置字符串(剑指Offer 第58题)
到了这里,关于C++题解 | 逆波兰表达式相关的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!