表达式求值

#include <iostream>
#include <cstring>
#include <string>
#include <cctype>
#include <algorithm>
#include <stack>
#include <map>
#include <sstream>
using namespace std;
//只作为一个参考
//约定表达式都是合法的,且在一行内输入,并没有空格
//约定运算符有 + - * /(整除) ( ) 
//约定操作数都是一位正整数,没有负号

//获得前后两个的优先级
//右//   +  -  *  /  (  )  #
//左// + >  >  <  <  <  >  >
    // - >  >  <  <  <  >  >
    // * >  >  >  >  <  >  >
    // / >  >  >  >  <  >  >
    // ( <  <  <  <  <  =  >
    // ) >  >  >  >  x  >  >
    // # <  <  <  <  <  <  =
static const char map1[7][7]={
    {'>','>','<','<','<','>','>'},
    {'>','>','<','<','<','>','>'},
    {'>','>','>','>','<','>','>'},
    {'>','>','>','>','<','>','>'},
    {'<','<','<','<','<','=','>'},
    {'>','>','>','>','x','>','>'},
    {'<','<','<','<','<','<','='},
};
static map<char,int> map2;
void init_map(){
    map2.insert(make_pair('+',0));
    map2.insert(make_pair('-',1));
    map2.insert(make_pair('*',2));
    map2.insert(make_pair('/',3));
    map2.insert(make_pair('(',4));
    map2.insert(make_pair(')',5));
    map2.insert(make_pair('#',6));
}

char get(char before,char after){
    return map1[map2[before]][map2[after]];   
}
//1 op 0 num
string gettype(char c){
    if(isdigit(c)) return "number";
    else return "op";
}

int calculate(int a,int b,char op){
    switch (op)
    {
    case '+':
        return a+b;
    case '-':
        return a-b;
    case '*':
        return a*b;
    case '/':
        return a/b;  
    }
    exit(-1);
}

int main(){
    stack<char> ops;
    stack<int> s;
    string c;
    char t;
    init_map();
    cin>>c;
    c=c+"#";//#作为分隔符
    stringstream ss(c);
    ops.push('#');
    ss>>t;
    while (1)
    {
        //输入、处理都完成
        if(ops.top()=='#'&&t=='#') break;
        if(gettype(t)=="number") {
            s.push(t-'0');
            ss>>t;
        }
        else{
            switch (get(ops.top(),t))
            {
            case '<':
                ops.push(t);
                ss>>t;
                break;
            case '>':
                int x1,x2;
                char _op;
                x1=s.top();s.pop();
                x2=s.top();s.pop();
                _op=ops.top();ops.pop();
                //这里注意操作数的顺序,因为先进后出,所以x2在前面
                s.push(calculate(x2,x1,_op));
                break;
            case '=':
                ss>>t;
                ops.pop();
                break;
            }
        }
    }
    cout<<s.top()<<endl;
    // cout<<get('+','-')<<endl;
    return 0;
}

 

上一篇:PTA数据结构-02-线性结构2 一元多项式的乘法与加法运算


下一篇:Map2