讲解LeetCode第150题：逆波兰表达式求值（完整代码）
讲解LeetCode第150题：逆波兰表达式求值（完整代码）
序属秋秋秋
发布于 2025-12-18 14:52:26
发布于 2025-12-18 14:52:26
LeetCode第150题：逆波兰表达式求值
💻博主正在持续更新关于LeetCode的习题。 😽如果你觉得内容还不错，请多多点赞。 🐶如果你觉得对你有帮助，请多多收藏。（防止以后找不到了） 👨👩👧👦如果你想阅读更多的LeetCode习题讲解，请多多关注博主。
题目介绍
逆波兰表达式由波兰的逻辑学家卢卡西维兹提出。逆波兰表达式的特点是:
- 没有括号，即它不需要括号来指定操作的优先级。
- 运算符总是放在和它相关的操作数之后。
因此，逆波兰表达式也称后缀表达式。
在这里插入图片描述
方法一：栈
完整代码展示
//逆波兰表达式求值——栈
#include<iostream>
#include<vector>
#include<stack>
#include<string>
#include<cstdlib>
#include<stdexcept>
using namespace std;
class Solution {
public:
int evalRPN(vector<string>& tokens)
{
stack<int>stk;
for(const string& str :tokens)
{
if(isNumber(str))
{
stk.push(atoi(str.c_str()));
}
else
{
int num2=stk.top();
stk.pop();
int num1=stk.top();
stk.pop();
switch(str[0])
{
case '+':
stk.push(num1+num2);
break;
case '-':
stk.push(num1-num2);
break;
case '*':
stk.push(num1*num2);
break;
case '/':
if(num2==0)
{
throw runtime_error("除以零错误");
}
stk.push(num1/num2);
break;
default:
throw runtime_error("未定义运算符"+str);
}
}
}
return stk.top();
}
bool isNumber(const string& str)
{
return !(str=="+"||str=="-"||str=="*"||str=="/");
}
};
int main()
{
vector<string>tokens = { "4","13","5","/","+" };
Solution value;
int result = value.evalRPN(tokens);
cout << "逆波兰表达式的结果是：" << result << endl;
return 0;
}核心原理演示
输入：vector
<string>tokens = { “4”,“13”,“5”,“/”,“+” };
在这里插入图片描述
输出：6
代码片段解释
片段一：
在这里插入图片描述
片段二：
在这里插入图片描述
片段三：
在这里插入图片描述
片段四：
在这里插入图片描述
片段五：
在这里插入图片描述
方法二：数组模拟栈
完整代码展示
//逆波兰表达式求值——栈
#include<iostream>
#include<vector>
#include<string>
#include<cstdlib>
#include<cctype>
using namespace std;
class Solution {
public:
int evalRPN(vector<string>& tokens)
{
int n=tokens.size();
vector<int>stk((n+1)/2);
int index=-1;
for (string& str:tokens)
{
if(str.length()>1||isdigit(str[0]))
{
index++;
stk[index]=atoi(str.c_str());
}
else
{
switch(str[0])
{
case '+':
index--;
stk[index]+=stk[index+1];
break;
case '-':
index--;
stk[index]-=stk[index+1];
break;
case '*':
index--;
stk[index]*=stk[index+1];
break;
case '/':
index--;
stk[index]/=stk[index+1];
break;
}
}
}
return stk[index];
}
};
int main()
{
vector<string>tokens = { "4","13","5","/","+" };
Solution value;
int result = value.evalRPN(tokens);
cout << "逆波兰表达式的结果是：" << result << endl;
return 0;
}核心原理演示
输入：vector
<string>tokens = { “4”,“13”,“5”,“/”,“+” };
在这里插入图片描述
输出：6
代码片段解释
片段一：
在这里插入图片描述
片段二：
if(str.length()>1||isdigit(str[0]))
在这里插入图片描述
片段三：
int index=-1;
index++;
stk[index]=atoi(str.c_str());
index--;
stk[index]+=stk[index+1];
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-10-18，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
