使用四个双端队列+辅助栈
题目描述
链接：https://ac.nowcoder.com/acm/problem/50999 来源：牛客网
给出一个表达式,其中运算符仅包含+,-,*,/,^（加 减 乘 整除 乘方）要求求出表达式的最终值数据。可能会出现括号情况，还有可能出现多余括号情况，数据保证不会出现 的答案，数据可能会出现负数情况。
输入描述:
仅一行，即为表达式
输出描述
仅一行，既为表达式算出的结果
思路
使用双端队列，其中
-
std::deque<int> numsQueue用来存储表达式中的数字； -
std::deque<char> charQueue用来存储除括号以外的所有运算符； -
std::deque<int> helpNumQueue;std::deque<char> helpCharQueue; 用来处理作为最高优先级运算符的括号的辅助队列； -
std::stack<int> record; 记录一对括号中参与运算后的数字个数，在使用辅助队列时从队列弹回相应个数的数字； -
std::stack<char> parenthessRecord; 记录左括号的使用情况，当栈里只有一个‘(’，并且之后遇到的第一个括号是‘)’时，弹出‘(’; -
int parentheses; 记录成对括号的使用情况，遇到‘(’记录加1，遇到‘)’记录减一。
优先级处理，除括号之外，乘方的优先级最高，其次为乘除，最后为加减。计算乘方、乘除、加减时分别使用了三个函数：
-
void insideParenthPow() 计算乘方 -
void insideParenth1() 计算乘除 -
void insideParenth2() 计算加减
每次对括号内的表达式进行计算时使用bool hasOperational(char ch)函数判断charQueue中有无目标运算符，先检查乘方运算符，其次是乘除，前两者计算完毕后必然剩下加减运算符，根据返回的条件开展计算，最终使用void insideParentTotal()得到括号内的运算结果：
void insideParentTotal(){
if(this->hasOperational('^')) this->insideParenthPow();
if(this->hasOperational('*')||this->hasOperational('/')){
this->insideParenth1();
}
this->insideParenth2();
}
对题目中的负数的处理：遍历输入字符串中的‘-’，若是字符串前面不为数字，且不为右括号‘)’，则在‘-’前面加上一个字符‘0’。函数实现如下。
std::string addZero(std::string aString){
int length=aString.size();
std::string temp;
for(int i=0;i<length;i++){
if(i==0){
if(aString[i]=='-') temp+='0';
}
else{
if(aString[i]=='-'
&&!this->isNumber(aString[i-1])&&aString[i-1]!=')')
temp+='0';
}
temp+=aString[i];
}
return temp;
}
一些辅助函数：
-
bool isNumber(char ch) 判断字符是否为数字 -
void printNumsQueue() 打印当前std::deque<int> numsQueue中的内容 -
void printCharQueue() 打印当前std::deque<char> charQueue中的内容 -
std::string getNumber(int &start,std::string expression) 从字符串中提取数字 -
void getTrueNumber(std::string expression,char ch,int &i) 函数命名和作用严重不符合，函数实现将数字和运算符分别放入对应的队列中，遇到‘(’或 ‘)’结束 -
void toHelpQueue(int lengthOfNumQueue) 将当前队列中的数字和运算符按照自定义长度放入辅助队列中 -
void toUsingQueue(int lengthOfHelpQueue) 将辅助队列中的数字和运算符按照自定义的长度放入当前的队列中 -
void NotAddAndDiff(int queueCount) void insideParenth1()中使用的函数，实现对当前队列中数字的乘除运算；最终，使用int calculate(std::string expression)函数遍历一遍处理过符号‘-’的字符串，对括号和相关的数字和运算符进行计算，并返回最后的计算结果。完整代码如下：
//#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <deque>
#include <stack>
#include <cmath>
class mySolution{
private:
std::deque<int> numsQueue;
std::deque<char> charQueue;
std::deque<int> helpNumQueue;
std::deque<char> helpCharQueue;
std::stack<int> record;
std::stack<char> parenthessRecord;
int parentheses;
public:
bool isNumber(char ch){
if(ch>='0'&&ch<='9') return true;
else return false;
}
std::string addZero(std::string aString){
int length=aString.size();
std::string temp;
for(int i=0;i<length;i++){
if(i==0){
if(aString[i]=='-') temp+='0';
}
else{
if(aString[i]=='-'&&!this->isNumber(aString[i-1])&&aString[i-1]!=')') temp+='0';
}
temp+=aString[i];
}
return temp;
}
void printNumsQueue(){
int length=this->numsQueue.size();
while(length--){
std::cout<<this->numsQueue.front()<<" ";
this->numsQueue.push_back(this->numsQueue.front());
this->numsQueue.pop_front();
}
std::cout<<std::endl;
}
void printCharQueue(){
int length=this->charQueue.size();
while(length--){
std::cout<<this->charQueue.front()<<" ";
this->charQueue.push_back(this->charQueue.front());
this->charQueue.pop_front();
}
std::cout<<std::endl;
}
std::string getNumber(int &start,std::string expression){
int originStart=start;
int length=expression.size();
while(this->isNumber(expression[start])&&start<length){
start++;
}
auto temp=expression.substr(originStart,start-originStart);
return temp;
}
void getTrueNumber(std::string expression,char ch,int &i){
int length=expression.size();
while(expression[i]!=ch&&i<length){
if(this->isNumber(expression[i])){
auto nums=std::stoi(this->getNumber(i,expression));
this->numsQueue.push_back(nums);
}
if(expression[i]=='('||expression[i]==')') break;
if(!this->isNumber(expression[i])&&i<length){
this->charQueue.push_back(expression[i]);
}
i++;
}
}
void NotAddAndDiff(int queueCount){
int temp=this->numsQueue.front();
numsQueue.pop_front();
while(!this->charQueue.empty()&&this->charQueue.front()!='+'&&this->charQueue.front()!='-'){
if(this->charQueue.front()=='*') temp*=numsQueue.front();
else if(this->charQueue.front()=='/') temp/=numsQueue.front();
this->numsQueue.pop_front();
this->charQueue.pop_front();
}
this->numsQueue.push_front(temp);
for(int i=0;i<queueCount;i++){
this->charQueue.push_front(this->charQueue.back());
this->numsQueue.push_front(this->numsQueue.back());
this->charQueue.pop_back();
this->numsQueue.pop_back();
}
}
bool hasOperational(char ch){
int length=this->charQueue.size();
bool has=false;
while(length--){
this->charQueue.push_back(this->charQueue.front());
if(ch==this->charQueue.front()) has=true;
this->charQueue.pop_front();
}
return has;
}
void insideParenthPow(){
int size=charQueue.size();
int queueCount=0;
while(this->hasOperational('^')){
if(this->charQueue.front()!='^'){
this->charQueue.push_back( this->charQueue.front());
this->charQueue.pop_front();
this->numsQueue.push_back( this->numsQueue.front());
this->numsQueue.pop_front();
queueCount++;
}
else{
int temp=this->numsQueue.front();
numsQueue.pop_front();
while(!this->charQueue.empty()&&this->charQueue.front()=='^'){
temp=std::pow(temp,this->numsQueue.front());
this->numsQueue.pop_front();
this->charQueue.pop_front();
}
this->numsQueue.push_front(temp);
for(int i=0;i<queueCount;i++){
this->charQueue.push_front(this->charQueue.back());
this->numsQueue.push_front(this->numsQueue.back());
this->charQueue.pop_back();
this->numsQueue.pop_back();
}
queueCount=0;
}
}
}
void insideParenth1(){
int queueCount=0;
while(this->hasOperational('*')||this->hasOperational('/')){
if(this->charQueue.front()!='*'&&this->charQueue.front()!='/'){
this->charQueue.push_back( this->charQueue.front());
this->charQueue.pop_front();
this->numsQueue.push_back( this->numsQueue.front());
this->numsQueue.pop_front();
queueCount++;
}
else{
this->NotAddAndDiff(queueCount);
queueCount=0;
}
}
}
void insideParenth2(){
int sum=this->numsQueue.front();
this->numsQueue.pop_front();
while(!charQueue.empty()){
if(this->charQueue.front()=='+') sum+=this->numsQueue.front();
else sum-=this->numsQueue.front();
this->numsQueue.pop_front();
this->charQueue.pop_front();
}
this->numsQueue.push_front(sum);
}
void insideParentTotal(){
//1111111=========================
//this->printNumsQueue();
//this->printCharQueue();
if(this->hasOperational('^')) this->insideParenthPow();
//222222=========================
//this->printNumsQueue();
//this->printCharQueue();
if(this->hasOperational('*')||this->hasOperational('/')){
this->insideParenth1();
}
//333333333=========================
//this->printNumsQueue();
//this->printCharQueue();
this->insideParenth2();
//44444444444=========================
//this->printNumsQueue();
//this->printCharQueue();
}
void toHelpQueue(int lengthOfNumQueue){
while(lengthOfNumQueue--){
this->helpNumQueue.push_back(this->numsQueue.front());
this->helpCharQueue.push_back(this->charQueue.front());
this->numsQueue.pop_front();
this->charQueue.pop_front();
}
}
void toUsingQueue(int lengthOfHelpQueue){
while(lengthOfHelpQueue--){
this->numsQueue.push_front(this->helpNumQueue.back());
this->charQueue.push_front(this->helpCharQueue.back());
this->helpNumQueue.pop_back();
this->helpCharQueue.pop_back();
}
}
int calculate(std::string expression){
expression=this->addZero(expression);
int length=expression.size();
int i=0;
while(i<length){
if(expression[i]=='('){
while(expression[i]=='(') {
this->parenthessRecord.push('(');
this->parentheses++;
i++;
}
this->getTrueNumber(expression,')', i);
if(expression[i]=='('){
this->record.push(this->numsQueue.size());
this->toHelpQueue(this->numsQueue.size());
}
else{
this->insideParentTotal();
while(expression[i]==')') {
if(this->parenthessRecord.size()==1) this->parenthessRecord.pop();
this->parentheses--;i++;
}
if(this->parentheses<=0){
if(!this->record.empty()){
int temp=this->record.top(); this->record.pop();
this->toUsingQueue(temp);
if(this->parentheses==0){
if(i<=length&&!this->parenthessRecord.empty())
{ this->insideParentTotal(); }
while(!this->parenthessRecord.empty()){
this->parenthessRecord.pop();
}
}
}
}
}
}
if(expression[i]!='('){
this->getTrueNumber(expression,'(', i);
if(expression[i]=='('){
this->record.push(this->numsQueue.size());
this->toHelpQueue(this->numsQueue.size());
}
if(expression[i]!='('){
this->insideParentTotal();
if(expression[i]==')'){
if(this->parenthessRecord.size()==1) this->parenthessRecord.pop();
this->parentheses--;
}
i++;
}
}
}
while(!this->helpNumQueue.empty()){
while(!this->record.empty()){
int temp=this->record.top(); this->record.pop();
this->toUsingQueue(temp);
this->insideParentTotal();
}
}
this->insideParentTotal();
return this->numsQueue.front();
}
};
int main(){
mySolution*solution=new mySolution();
std::string expression;
while(std::cin>>expression){
int answer=solution->calculate(expression);
std::cout<<answer<<std::endl;
}
delete solution;
return 0;
}
其实我觉得代码应该更精简，逻辑更清晰，其中最难处理的是多余的括号，以至于我不断调试，使用大佬们的代码找通不过的案例，最后弄得我极其混乱,决定不再挣扎之后，竟然让我发现了处理‘-’号时，前面有‘)’时就不要加‘0’了这个最后通不过的17.7%，然后又又又加了限制条件之后居然通过了！喜大普奔！所以我决定写一个题解来记录一下这个平凡的下午。 大佬们还是强！另外，确实，这个多余的括号是怎么分类的呢？测试一位大佬简洁的递归代码，这个示例是通不过的,算出来不是27,但是他的代码可以完美通过。 牛客为什么不能像力扣那样，直接显示通不过的案例呢，这样也方便调试，不用自己穷尽思路想案例！
京公网安备 11010502036488号