猿创征文 |【算法入门必刷】数据结构-栈（四）

📦个人主页：一二三o-0-O的博客
🏆技术方向：C/C++客户端资深工程师（直播+音视频剪辑）
👨‍💻作者简介：数据结构算法与音视频领域创作者
📒 系列专栏：牛客网面试必刷
📣专栏目标：帮助伙伴们通过系统训练，掌握数据结构与算法，收获心仪Offer
📝推荐一个找工作神器：牛客刷题网 【面试经验|实习招聘内推，求职就业一战解决】
🧡如果对您有帮助的话，欢迎点赞👍收藏📂，关注不迷路

【算法入门必刷】数据结构-栈篇系列文章：
【算法入门必刷】数据结构-栈（一）
【算法入门必刷】数据结构-栈（二）
【算法入门必刷】数据结构-栈（三）
【算法入门必刷】数据结构-栈（四）
【算法入门必刷】数据结构-栈（五）
【算法入门必刷】数据结构-栈（六）

前言

开启刷题，请点击右边链接进行跳转点击这里

算法入门刷题训练

AB4：逆波兰表达式求值

题目分析

描述
给定一个逆波兰表达式，求表达式的值。
数据范围：表达式长度满足 10^4 \1≤n≤10 ，表达式中仅包含数字和 + ，- , * , / ，其中数字的大小满足 ∣val∣≤200 。

根据题目描述，本题是典型的栈的应用。维护一个辅助栈，遍历字符串，遇到数字将其入栈；遇到符号，从栈中弹出两个元素进行计算，并且将计算后的结果从新入栈作为下一次运算的数字。

理论准备

首先我们要掌握stack的一些基础操作：

-----将元素入栈-----
std::stack mystack;
// 依次将元素1-10入栈
for (int i=1;i<=10;i++) mystack.push(i);

-----判断stack是否为空-----
std::stack mystack;
for (int i=1;i<=10;i++) mystack.push(i);
// 如果栈不为空，进入循环
while (!mystack.empty())
{
}

----获取stack中元素数量-----
std::stack mystack;
for (int i=1;i<=10;i++) mystack.push(i);
// 获取数量
int size = mystack.size();

-----获取栈顶元素-----
std::stack mystack;
for (int i=1;i<=10;i++) mystack.push(i);
// 获取栈顶元素
int topNum = mystack.top();

-----弹出栈顶元素-----
std::stack mystack;
int sum (0);
for (int i=1;i<=10;i++) mystack.push(i);
while (!mystack.empty())
{
sum += mystack.top();
// 弹出栈顶元素
mystack.pop();
}
std::cout << "total: " << sum << ‘\n’;

题解

具体的解决方案如下：

1. 声明辅助栈

// 声明辅助栈
stack<int> st;
// 获取字符串数量
int n = tokens.size();
1
2
3
4

2. 遍历字符串，遇到数字将其入栈

for(int i{};i<n;++i){
    string op = tokens[i];
    
    if(op == "+" ||
      op == "-" ||
      op == "*" ||
      op == "/"){
        
    }else{ // 数字，直接将其入栈
        st.push(stoi(op));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

3. 遇到符号，从栈中弹出两个元素进行计算，并且将计算后的结果从新入栈作为下一次运算的数字

for(int i{};i<n;++i){
	string op = tokens[i];
	
	if(op == "+" ||
	  op == "-" ||
	  op == "*" ||
	  op == "/"){
	  	// 从栈顶弹出两个数字
	    int num1 = st.top();st.pop();
	    int num2 = st.top();st.pop();
	    // 将计算后的结果从新入栈，作为下一次运算的数字
	    if(op == "+") st.push(num2 + num1);
	    if(op == "-") st.push(num2 - num1);
	    if(op == "*") st.push(num2 * num1);
	    if(op == "/") st.push(num2 / num1);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4. 完整代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param tokens string字符串vector 
     * @return int整型
     */
    int evalRPN(vector<string>& tokens) {
        // write code here
        stack<int> st;
        int n = tokens.size();

        for(int i{};i<n;++i){
            string op = tokens[i];
            
            if(op == "+" ||
              op == "-" ||
              op == "*" ||
              op == "/"){
                int num1 = st.top();st.pop();
                int num2 = st.top();st.pop();
                
                if(op == "+") st.push(num2 + num1);
                if(op == "-") st.push(num2 - num1);
                if(op == "*") st.push(num2 * num1);
                if(op == "/") st.push(num2 / num1);
            }else{
                st.push(stoi(op));
            }
        }
        
        return st.top();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

当提交成功后，会展示如下界面，那么恭喜这道题目就通过了！

小结

祝愿所有的伙伴都能拿到自己心仪的Offer！📣伙伴们点击右边链接立刻开启刷题吧：牛客——刷题网