计蒜客题目 加减乘除

给出一个表达式,其中运算符仅包含 +,-,*,/,^要求求出表达式的最终值在这里，/ 为整除最终结果为正整数,数据保证不需要使用高精度！

输入仅一行，即为表达式。

输出仅一行，既为表达式算出的结果 结果小于 long int 的最大范围，且整个计算的过程中，也不会超过 long int 的最大范围。

表达式总长度 ≤20≤20

样例输入

2^3+1

样例输出

9

#include<stack>
#include<string>
#include<iostream>
#include<math.h>

using namespace std;

int pror[4][4]={//优先级数组，int[i][j]=1表示i比j的优先级高
    0,0,0,0,//+ 0
    1,0,0,0,//* 1
    1,0,0,0,// / 2
    1,1,1,0,//^ 3
};

int inputconvert(char c){//对输入运算符的转换
    switch(c){
        case '+': return 0;
        case '*': return 1;
        case '/': return 2;
        case '^': return 3;
    }
}

int main(){
    string str;//输入的字符串
    cin>>str;
    stack<double> num;//存放数的栈
    stack<int> op;//存放运算符的栈
    double result;//存放运算结果
    bool flag=0;//用来标示减号，flag=1是减号
    for(int i=0;i<str.size();i++){//一直输入直到全部输入完毕
        if(str[i]>='0' && str[i]<='9'){//如果当前是数字
            double inum=(long int)(str[i]-'0');
            while(str[i+1]>='0' && str[i+1]<='9' && (i+1)<str.size()){//如果下一个数字仍然是数字
                inum*=10;
                inum+=(double)(str[i+1]-'0');
                i++;
            }
            if(flag==1) {
                inum=-inum;
                flag=0;
            }
            num.push(inum);
        }
        else{//如果当前是符号
            if(str[i]=='-'){//对减号的特殊处理
                str[i]='+';
                flag=1;
            }
            int inpx=inputconvert(str[i]);//inpx记录转换为数字的运算符
            if(!op.empty()){//如果符号栈非空
                int temp=op.top();
             	while(pror[temp][inpx]==1){//栈顶的运算符优先级比当前的高
                    op.pop();//符号栈去掉顶部
                    double a=num.top();//用a,b两个变量记录最顶的2个数字，注意b先入栈
                    num.pop();
                    double b=num.top();
                    num.pop();
                    switch(temp){
                        case 0: {result=b+a; break;}
                        case 1: {result=b*a; break;}
                        case 2: {result=b/a; break;}
                        case 3: {result=pow(b,a); break;}
                    }
                    num.push(result);//将计算结果放入数字栈
                    if(op.empty()) break;//如果此时符号栈已经空了
                    else temp=op.top();//更新temp中保存的栈顶运算符
                }                
            }
            op.push(inpx);//新的符号压入栈            
        }
    }
    while(!num.empty()){//如果数字栈非空
        double a=num.top();//用a,b两个变量记录最顶的2个数字，注意b先入栈
        num.pop();
        double b=num.top();
        num.pop();
        int optemp=op.top();//用optemp记录栈顶符号
        op.pop();
        switch(optemp){
            case 0: {result=b+a; break;}
            case 1: {result=b*a; break;}
            case 2: {result=b/a; break;}
            case 3: {result=pow(b,a); break;}
        }
        if(num.empty()) break;//如果数字栈空了
        num.push(result);//数字栈不空，将此次计算结果放入数字栈
    }
    cout<<(int)result;
    
    return 0;
}

解题思路：

从前往后遍历字符串，把数字和运算符分别压入不同的栈。压入运算符的时候注意比较当前的运算符和栈顶运算符的优先级，若当前优先级低，则先计算一次，并把结果压入数字栈，循环直到当前运算符优先级不低于栈顶运算符。一直遍历到字符串结束。此时已经先将优先级高的运算算完了，所以可以在数字栈有数字的时候，一个一个pop出来计算，直到数字栈空。

有几个需要注意的点：

1、比较优先级，使用了一个数组。其实也可以考虑这样：

switch(str[i]){
    case '+': op="01"; break;
    case '-': op="02"; break;
    case '*': op="11"; break;
    case '/': op="12"; break;
    case '^': op="21"; break;
}

用不同的字符串代表符号，第一位表示优先级，第二位表示具体是哪个符号

2、对减号的特殊处理。原先写的代码中，符号是有减号的，但是发现这样无法计算连减的情况。例如计算2-3-4，由于3、4均压入栈，会先计算3-4，得到-1压入栈，再计算2-(-1)=3，和实际情况不符合。考虑修改为：遇到减号则置标志flag=1，同时当前运算符变为+，下一个压入的数字变为原先数字的负数。这里要注意，对减号的处理仍然要满足判断优先级，不能直接在这里压入一个+号运算符。

3、一开始做的时候由于没有要求精度，我就都用了long int类型，但是发现这样的话，计算的时候精度会丢失。例如计算3*1/3，由于先计算1/3，如果用long int类型，得到结果为0，压入栈，下一步计算3*0=0，不符合实际情况。考虑修改为：在计算过程中使用double类型，最后输出时，输出int类型。

总结：

只能通过2组测试，实在想不到哪里有问题了……

虽然是栈的使用练习，但是不写出来真的有一堆问题发现不了，还是要多练！