2、AB4 逆波兰表达式求值
题目链接：逆波兰表达式求值
题目描述：
2.1、解题思路
所谓逆波兰表达式就是：操作数在前，操作符在后， 2 - 1 相当于2 1 -，采用辅助栈：
遍历字符串，如果对应的字符不等于四则运算符，将操作数入栈
如果字符为四则运算符，取栈顶后出栈再取栈顶，根据运算符将不同运算结果入栈
遍历结束后的栈顶元素就是逆波兰表达式最终结果
2.2、代码实现与解析
本题源码：
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串vector * @return int整型 */ int evalRPN(vector<string>& s) { stack<int> stk; for (int i = 0; i < s.size(); i++) { if (s[i] == "+" || s[i] == "-" || s[i] == "*" || s[i] == "/") { int x1 = stk.top(); stk.pop(); int x2 = stk.top(); stk.pop(); if (s[i] == "+") stk.push(x1 + x2); if (s[i] == "-") stk.push(x2 - x1); if (s[i] == "*") stk.push(x1 * x2); if (s[i] == "/") stk.push(x2 / x1); } else { stk.push(stoi(s[i])); } } return stk.top(); } };
重要注释：
非四则运算符的话将字符串转化为整型后入栈，stoi可用于将字符型转化为整型
取栈顶后需要出栈一次才能再次取栈顶，这样才是两个连续的操作数
进行减法和除法时要让第二个栈顶在前，记住栈先进后出的特点
3、AB5 点击消除
题目链接：点击消除
题目描述：
3.1、解题思路
简单来说就是将相邻且相同的字符消除，采用辅助栈即可：
辅助栈空时直接入栈
后续遍历时若栈顶元素与之相等就出栈，不等就入栈
判断最终栈的情况：
若栈空，输出0
若栈不空，输出栈内字符串
3.2、代码实现与解析
本题源码：
#include <iostream> #include <stack> using namespace std; int main() { string s, res; cin >> s; stack<char>stk; for (int i = 0; i < s.size(); i++) { if (!stk.empty() && stk.top() == s[i]) { stk.pop(); } else { stk.push(s[i]); } } if (stk.empty()) cout << 0; else { while (!stk.empty()) { res = stk.top() + res; stk.pop(); } cout << res; } }
重要注释：
此题是自己设计输入输出，使用辅助栈需要包含头文件：<stack>
由于栈是先进后出，因此采用字符串拼接：res = stk.top() + res来得到正序字符串
核心点在于入栈和出栈的条件，这点掌握就没问题了
欢迎大家订阅专栏，学习算法思想，合理利用牛客网，百炼成神！
