【算法入门必刷】数据结构-栈（六）
- 前言
- 算法入门刷题训练
- 题目AB6：表达式求值
- 题目分析
- 理论准备
- 题解
- 小结
📦个人主页：一二三o-0-O的猿创博客
🏆技术方向：C/C++客户端资深工程师（直播+音视频剪辑）
👨💻作者简介：数据结构算法与音视频领域创作者
📒 系列专栏：牛客网面试必刷
📣专栏目标：帮助伙伴们通过系统训练，掌握数据结构与算法，征文栈收获心仪Offer
📝推荐一个找工作神器：牛客刷题网 【面试经验|实习招聘内推，算法数据求职就业一战解决】
🧡如果对您有帮助的入门话，欢迎点赞👍收藏📂，必刷关注不迷路
【算法入门必刷】数据结构-栈篇系列文章：
【算法入门必刷】数据结构-栈（一）
【算法入门必刷】数据结构-栈（二）
【算法入门必刷】数据结构-栈（三）
【算法入门必刷】数据结构-栈（四）
【算法入门必刷】数据结构-栈（五）
【算法入门必刷】数据结构-栈（六）
前言
开启刷题，结构请点击右边链接进行跳转点击这里
算法入门刷题训练
题目AB6：表达式求值
题目分析
请写一个整数计算器，猿创支持加减乘三种运算和括号。征文栈
数据范围：1000≤∣s∣≤100，算法数据保证计算结果始终在整型范围内
要求：空间复杂度： O(n)，入门时间复杂度 O(n)
根据题目描述，必刷本题需要支持对加减乘运算以及括号。结构考虑三个问题：
- 如何运算？
在之前的猿创篇章四中【算法入门必刷】数据结构-栈（四），我们掌握了使用栈结构来进行数字运算，征文栈本题依然可以使用一个辅助栈，算法数据多了要处理括号的状况。 - 括号问题处理？
对于括号，这里要引出一个新的思想：分治思想，在后续的递归回溯专栏、动态规划专栏、贪心算法专栏等算法中都会更详细的阐述这种思想。这里我们先简单引出将每个括号的运算都设定为一个子问题，然后进行递归运算，得到一个运算后的结果。 - 不同运算符的优先级问题？
先计算乘法，后运算加减。
理论准备
首先我们要掌握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’;
题解
具体的解决方案如下：
- 首先声明递归函数
// 两个参数：一个是字符串，一个是当前遍历的字符串下标vectorrecursive(string s,int index){ // 递归终止条件 if(/*当遇到右括号标明一个括号的子问题已经处理完了，便结束递归*/ 或者是 /*字符串遍历结束了*/){ } // 返回两个元素 1. 子问题的结果 2. 当前子问题处理结束后，遍历字符串的下标} - 声明一个辅助栈
// 声明一个辅助栈stackst;// 获取字符串的大小int n = s.size();// 初始化运算符默认为+号，即第一个数直接入栈char op{'+'};// 初始化遍历到字符串的下标int i{index}; - 遍历字符串，首先将字符串的数字转化为int，便于计算
for(;i- 遇到左括号，即遇到了子问题，进入递归
// 碰到左括号，递归处理if(s[i] == '('){ vectorres = recursive(s, i+1); // 子问题的运算结果 num = res[0]; // 子问题遍历结束后的下标 i = res[1]; if(i != n-1) continue;} - 判断当前运算符
switch(op){// 加减号先入栈case '+': st.push(num); break;case '-': // 相反数 st.push(-num); break;// 优先计算乘号case '*': int temp = st.top(); st.pop(); st.push(temp*num); break;}// 遇到右括号结束递归if(s[i] == ')') break;// 否则将当前运算符赋值给opelse op = s[i];- 将栈中剩余的元素相加
int sum = 0; // 栈中元素相加 while(!st.empty()){ sum += st.top(); st.pop(); }- 完整代码如下：
class Solution {public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 返回表达式的值 * @param s string字符串 待计算的表达式 * @return int整型 */ vectorrecursive(string s,int index){ stackst; int n = s.size(); int num{}; // 默认为+号，即第一个数直接入栈 char op{'+'}; int i{index}; for(;ires = recursive(s, i+1); num = res[0]; i = res[1]; if(i != n-1) continue; } switch(op){ // 加减号先入栈 case '+': st.push(num); break; case '-': // 相反数 st.push(-num); break; // 优先计算乘号 case '*': int temp = st.top(); st.pop(); st.push(temp*num); break; } num = 0; // 遇到右括号结束递归 if(s[i] == ')') break; else op = s[i]; } int sum = 0; // 栈中元素相加 while(!st.empty()){ sum += st.top(); st.pop(); } return vector{sum,i}; } int solve(string s) { // write code here return recursive(s,0)[0]; }}; 当提交成功后，会展示如下界面，那么恭喜这道题目就通过了！
小结
祝愿所有的伙伴都能拿到自己心仪的Offer！📣伙伴们点击右边链接立刻开启刷题吧：牛客——刷题网
