表达式求值+-*/

功能：能够实现+-*/运算。

思路：使用一个运算符栈和一个运算数栈，首先压入头部哨兵 ,

1）只要栈顶的符号的优先级小，就将当前运算符压栈；

2）栈顶优先级更高的话就将当前运算符出栈，如果是二目运算符就取出两个操作数，计算的结果压入操作数栈；当前运算符是左括号优先级最高，如果栈顶是左括号则优先级最低，当前运算符是右括号则优先级最低。

3）如果栈顶优先级相等，就是右括号或者尾部哨兵

相等的情况下，栈顶的优先级要大。

表达式求值+-*/

//实现 对 + - * /  的四则运算  

#include<iostream>  
#include<stack>  

using namespace std;

stack<char> OPND;// 运算数  
stack<char> OPTR;//运算符 

char cmp(char a, char b){//考虑情况  a是栈顶元素，b是当前元素
    if ((a == '(' && b == ')') || (a == b && a == '
')) {//左右括号的优先级相同，或者都是哨兵，这样表示一个括号运行完了
        return '=';
    }
    if (a == '
' || a == '(')//栈里面的左括号优先级是最低的
        return '<';

    if (b == '
' || b == ')') //当前运算符的右括号的优先级是最高的 
        return '>';
    
    if (b == '(') {//当前运算符是左括号优先级是最高的
        return '<';
    }
    int ta, tb;//+-是1,*/是2
    if (a == '+' || a == '-')  ta = 1;  else ta = 2;
    if (b == '+' || b == '-')  tb = 1;  else tb = 2;    
    return  ta < tb ? '<':'>';
    //这里隐含了一个情况 就是 如果ta==tb，此时应返回'>'; 栈顶的优先级要保证高 

}

char Opt(char a, char s, char b)
{
    char t;
    switch (s)
    {
    case '+':t = a - 48 + b - 48 + 48;
        break;
    case '-':t = a - 48 - (b - 48) + 48;
        break;
    case '*':t = (a - 48) * (b - 48) + 48;
        break;
    case '/':t = (a - 48) / (b - 48) + 48;
        break;
    }
    return t;
}
  
int main(){

    OPTR.push('
');    
    char c;
    c = getchar();
    while (c != '
' || OPTR.top() != '
')
    {
        if (c >= '0' && c <= '9') {
            OPND.push(c); 
            c = getchar(); 
        }
        else{//过滤不严 
            switch (cmp(OPTR.top(), c)){
            case '<': 
                OPTR.push(c); 
                c = getchar(); 
                break;
            case '=': 
                OPTR.pop(); 
                c = getchar(); 
                break;  
            case '>':
                char s = OPTR.top(); OPTR.pop();
                char a, b, count;
                b = OPND.top(); OPND.pop();
                a = OPND.top(); OPND.pop();
                count = Opt(a, s, b);
                OPND.push(count);
                break;
            }
        }
    }
    cout << OPND.top() << endl;
    system("pause");
    return 0;
}

表达式求值+-*/

相关推荐