题解：AcWing 6031 计算

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing6031. 计算 - AcWing题库【题目描述】小明在你的帮助下破密了 Ferrari 设的密码门正要往前走突然又出现了一个密码门门上有一个算式其中只有()0-9-*/^求出的值就是密码。小明数学学得不好还需你帮他的忙。/用整数除法【输入】共1 11行为一个算式。【输出】共1 11行就是密码。【输入样例】1(32)*(7^26*9)/(2)【输出样例】258【算法标签】#栈#【代码详解】#includebits/stdc.husingnamespacestd;// 返回运算符c的优先级intpri(charc){switch(c){case(:// 左括号优先级最高{return5;}case^:// 幂运算{return4;}case*:// 乘法case/:// 除法{return3;}case:// 加法case-:// 减法{return2;}case):// 右括号优先级最低{return1;}}}// 计算 a 和 b 通过运算符 c 的结果intcalc(inta,intb,charc){switch(c){case:// 加法{returnab;}case-:// 减法{returna-b;}case*:// 乘法{returna*b;}case/:// 除法{returna/b;}case^:// 幂运算{returnpow(a,b);}}}intmain(){stackintnStk;// 数字栈stackcharcStk;// 运算符栈intnum0;// 当前正在读取的数字boolisNumfalse;// 标记是否正在读取数字string s;// 输入表达式cins;// 输入表达式s.push_back());// 在表达式末尾添加右括号确保最终计算for(inti0;is.length();i)// 遍历表达式{if(s[i]0s[i]9)// 如果是数字字符{numnum*10s[i]-0;// 构建多位数isNumtrue;// 标记正在读取数字}else// s[i]是运算符{if(isNum)// 如果之前正在读取数字{nStk.push(num);// 将完整数字压入数字栈num0;// 重置数字isNumfalse;// 标记数字读取结束}// 当运算符栈不为空且当前运算符优先级 栈顶运算符优先级// 且栈顶不是左括号时进行计算while(!(cStk.empty()||pri(s[i])pri(cStk.top())||cStk.top()()){// 从数字栈中弹出两个操作数intbnStk.top();nStk.pop();intanStk.top();nStk.pop();// 计算结果并压回数字栈nStk.push(calc(a,b,cStk.top()));// 弹出已使用的运算符cStk.pop();}// 处理括号匹配if(!cStk.empty()cStk.top()(s[i])){cStk.pop();// 弹出左括号}else{cStk.push(s[i]);// 将当前运算符压入栈}}}coutnStk.top();// 输出最终结果return0;// 程序正常结束}【运行结果】1(32)*(7^26*9)/(2) 258