题解 | #计算表达式#

#include<iostream>
#include<stack>
#include<vector>
#include<stdlib.h>
using namespace std;

int to_int(string s){
    int ans = 0;
    string::iterator it = s.begin();
    while(it!=s.end()){
        ans*=10;
        ans += *it-'0';
        it++;
    }
    return ans;
}
bool opGreater(char a,char b){//a>b
    if(a=='+'||a=='-') return false;
    if(b=='+'||b=='-') return true;
    return false;
}
bool isSameLevel(char a,char b){
    if(a=='+'||a=='-'){
        if(b=='+'||b=='-') return true;
    } else if(b=='*'||b=='/'){
        return true;
    }
    return false;
}
float cal(float a,float b,char o){
    switch(o){
        case '+':
            return a+b;
        case '-':
            return a-b;
        case '*':
            return a*b;
        case '/':
            return a/b;
    }
    return 0;
}
void cal(stack<float> &operand,stack<char> &op){
    float right = operand.top();
    operand.pop();
    float left = operand.top();
    operand.pop();
    char o = op.top();
    op.pop();
    float ans = cal(left,right,o);
    operand.push(ans);
}
void Question5_2(){//习题5.2  上海交大  计算无括号的中缀表达式
    string expression;
    while(cin>>expression){
        //初始化表达式序列
        vector<string> seq;
        int j = 0;
        int len = expression.size();
        for(int i=0;i<len;i++){
            if(expression[i]=='+'||expression[i]=='-'||expression[i]=='*'||expression[i]=='/'){
                //取操作数
                string num = expression.substr(j,i-j);
                seq.push_back(num);
                //取操作符
                string op = expression.substr(i,1);
                seq.push_back(op);
                j = i+1;
            }
        }
        seq.push_back(expression.substr(j));//取最后一个操作数
        
        //遍历表达式序列
        stack<float> operand;
        stack<char> op;
        vector<string>::iterator it = seq.begin();
        while(it!=seq.end()){
            if(*it=="+"||*it=="-"||*it=="*"||*it=="/"){//存入操作符栈
                if(op.size()==0||opGreater((*it)[0],op.top())){
                             //优先级升高，如1+2*3，暂时不算*
                    op.push((*it)[0]);
                } else if(isSameLevel((*it)[0],op.top())){
                              //优先级不变，如1+2*3*4，算2*3
                    cal(operand,op);
                    op.push((*it)[0]);
                } else {//优先级降低，如1+2*3*45，算6*4
                    while(!op.empty()){
                        cal(operand,op);
                    }
                    op.push((*it)[0]);
                }
            } else {//操作数，转化成数字形式后压入操作数栈
                operand.push((float)to_int(*it));
            }
            it++;
        }
        while(!op.empty()){
            cal(operand,op);
        }
        cout<<operand.top()<<endl;
    }
    
}
int main(){
    Question5_2();
}