题解 | #四则运算#
四则运算
https://www.nowcoder.com/practice/9999764a61484d819056f807d2a91f1e
原思路:
分三个部分,分别处理括号,乘除,加减。但是处理括号内部信息的时候,设计到乘除和加减的处理,无法解决(PASS)
题解思路:
简化:
三个不同的右括号,本质相同表现形式为相对顺序,可以统一为右括号。
输入:
使用数据栈和运算栈分别保存数字、运算符
算法:
加减与乘除运算的优先级,四则与括号运算的优先级
总结为先处理乘除与加减的优先级;后处理括号的优先级。
(1)乘除与加减(可看为无括号时的简化版),若当前运算的优先级小于等于上个优先级,则处理上个运算;如(3*5-2,3*5*5,3-3-3)
具体在栈中操作。若栈中的优先级大于等于当前优先级,则pop数据和运算符进行处理。(3-3*5+3)
好处1:在遇到右括号之前,左括号据当前的元素中,剩下的乘除法只可能在最后,且唯一。
好处2:从左向右计算,对于(12-5-7+3)不会出现结果为17的错误。
(2)右括号,遇到右括号时,从双栈中取元素进行计算。
遍历栈中的元素,若优先级符合且不为'(',执行操作。
操作后,pop栈首的'(',完成一个括号的内容。
注意,操作后此时只有一种情况未被处理,即a +- b* / c。
且乘除仅可能有一个,紧靠右括号会被优先处理。
(3)遍历字符串时,会有四种情况,左括号,数字,运算符,右括号。
左括号,压入
数字,压入,
运算符,比较优先级并计算,完成没有括号的主要部分。
右括号,比较栈首优先级并计算,计算完成后pop出'(',完成一个括号的内容
细节:
在遍历字符串的4种可能中。根据 数字-运算符-数字顺序 处理,节省编写判别是否数字函数,
处理数字时,可能存在'-'前缀,以及多位数。
处理运算符和括号时的运算操作,封装成函数。
在遍历右括号时,如取元素和运算符执行,直到遇到左括号;执行完成后释放左括号
优先级比较函数中,除非前+- 后* /,否则返回true。同时,首个运算符前面可能存在'('
边界条件,到最后i = s.size()时,可能还存在 a + b * c等函数,需要使用while搭配deal_ite进一步处理
测试用例:
(7+5*4*3+6), 7+5*4*3+6, 3+2*{1+2*[-4/(8-6)+7]}
#include <iostream> #include <stack> using namespace std; bool cmp(char &c1, char &c2){ // 除非前+- 后*/,否则返回true。同时,首个运算符前面可能存在'(' if(c1 == '(') return false; if((c1 == '+' || c1 == '-') && (c2 == '*' || c2 == '/')) return false; return true; } int deal_op(int &left, char &op, int &right){ if(op == '+') return left + right; if(op == '-') return left - right; if(op == '*') return left * right; return left / right; } void deal_ite(stack<int> &intes, stack<char> &ops){ int right = intes.top(); intes.pop(); int left = intes.top(); intes.pop(); char op = ops.top(); ops.pop(); int cur = deal_op(left, op, right); // cout << cur << endl; intes.push(cur); } int main(){ string s; cin >> s; stack<int> intes; stack<char> ops; bool isCurOp = false; string noNum = "+-/*()[]{}"; // ([{ 前一般会接运算符,也可不用考虑 for(int i = 0; i <= s.size(); i++){ if(i == s.size()) { while(!ops.empty() && ops.top() != '(')deal_ite(intes, ops); continue; } // cout << i << " " << s.size() << " " << s[i] << endl; // printf("i:%d\n", i); // printf()实时刷新,需要搭配fflust(stdout); if(s[i] == '(' || s[i] == '[' || s[i] == '{'){ ops.push('('); // 统一为'(' } else if(s[i] == ')' || s[i] == ']' || s[i] == '}'){ // 可能还剩余a-b*c的运算,同时ops中保存有'(' while(!ops.empty() && ops.top() != '(') { deal_ite(intes, ops); } // 括号内计算完成后,释放左括号 if(ops.top() == '(') ops.pop(); } else if(isCurOp){ // 当前为运算符,若当前运算符小于等于前一个运算符(保存在栈中),计算上一个运算符 while(!ops.empty() && cmp(ops.top(), s[i])){ deal_ite(intes, ops); } ops.push(s[i]); isCurOp = false; }else{ // 当前为数字。可能存在'-'前缀,以及多位数。 int j = i; if(s[j] == '-') j++; while(j < s.size() && noNum.find(s[j]) == noNum.npos) j++; intes.push(stoi(s.substr(i, j-i))); i = j - 1; isCurOp = true; } } cout << intes.top() << endl; }