首页 > 代码库 > STL栈的应用之表达式求值

STL栈的应用之表达式求值


#include<iostream>
#include<cstring>
#include<cstdio>
#include<stack>

using namespace std;

/*************
 *计算
*************/

int operate(int a, char op, int b ){
    if(op == ‘+‘) return a+b;
    else if(op == ‘-‘) return a-b;
    else if(op == ‘*‘) return a*b;
    else if(op == ‘/‘) return a/b;
}

/**************
 *比較优先级
**************/

char precede(char a, char b){
    if(a==‘+‘ || a==‘-‘){
        if(b==‘*‘ || b==‘/‘ || b==‘(‘) return ‘<‘;
        else if(b==‘)‘ || b==‘+‘
                || b==‘-‘ || b==‘#‘) return ‘>‘;
    }

    else if(a==‘*‘ || a==‘/‘){
        if(b==‘(‘) return ‘<‘;
        else if(b==‘+‘ || b==‘-‘ || b==‘*‘
                || b==‘/‘ || b==‘)‘ || b==‘#‘) return ‘>‘;
    }

    else if(a==‘(‘){
        if(b==‘+‘ || b==‘-‘ || b==‘*‘
           || b==‘/‘ || b==‘(‘) return ‘<‘;
        else if(b==‘)‘) return ‘=‘;
    }

    else if(a==‘)‘){
        if(b==‘+‘ || b==‘-‘ || b==‘*‘
           || b==‘/‘ || b==‘#‘ || b==‘)‘) return ‘>‘;
    }

    else if(a==‘#‘){
        if(b==‘+‘ || b==‘-‘ || b==‘*‘ ||
           b==‘/‘ || b==‘#‘ || b==‘(‘) return ‘<‘;
    }
}

/**********************
 *推断是否为数字字符
**********************/

bool judge(char a){
    if(a>=‘0‘ && a<=‘9‘)return true;
    else return false;
}

/***************
 *Main函数
***************/

int main()
{
    stack<int>op_n;
    stack<char>op_s;
    char str, ans;
    int num = 0;
    bool flag = false;
    op_s.push(‘#‘);
    cin >> str;

    while(str!=‘#‘ || op_s.top()!=‘#‘){
        if(judge(str)){
            flag = true;
            num = num*10 + (str-‘0‘);   /*处理多位数数据*/
            cin >> str;
        }else{
            if(flag){
                flag = false;
                op_n.push(num);
                num = 0;
            }
            ans = precede(op_s.top(), str);
            if(ans == ‘<‘){
                op_s.push(str);
                cin>>str;
            }

            if(ans == ‘=‘){
                op_s.pop();
                cin >> str;
            }

            if(ans == ‘>‘){
                int a;int b;char c;
                b = op_n.top();op_n.pop();
                a = op_n.top();op_n.pop();
                c = op_s.top();op_s.pop();
                cout << a << ‘ ‘ << c
                << ‘ ‘ << b << endl;
                op_n.push( operate(a, c, b) );
            }
        }
    }
    cout << op_n.top() << endl;
    return 0;
}



 

STL栈的应用之表达式求值