总时间限制: 200ms 内存限制: 1024kB

描述
人们熟悉的四则运算表达式称为中缀表达式，例如(23+34*45/(5+6+7))。在程序设计语言中，可以利用堆栈的方法把中缀表达式转换成保值的后缀表达式（又称逆波兰表示法），并最终变为计算机可以直接执行的指令，得到表达式的值。

给定一个中缀表达式，编写程序，利用堆栈的方法，计算表达式的值。

输入:
第一行为测试数据的组数N
接下来的N行，每行是一个中缀表达式。表达式中只含数字、四则运算符和圆括号，操作数都是正整数，数和运算符、括号之间没有空格。中缀表> 达式的字符串长度不超过600。

输出:
对每一组测试数据输出一行，为表达式的值

样例输入:
3
3+5*8
(3+5)*8
(23+34*45/(5+6+7))

样例输出:
43
64
108

提示
注意：运算过程均为整数运算（除法运算‘/‘即按照C++定义的int除以int的结果，测试数据不会出现除数为0的情况），输出结果也为整数（可能为负）。
中间计算结果可能为负。

解题思路：先转换成后缀表达式，再对后缀表达式求值。

转换成后缀表达式：

1. 遇到操作数直接输出
2. 遇到操作符直接压入栈中
3. 遇到右括号不断弹出操作符直到遇到左括号
4. 遇到操作符不断弹出直到遇到优先级更低的操作符
5. 输入完毕后弹出栈内所有元素

计算后缀表达式

1. 遇到操作数直接压入栈
2. 遇到操作符就从栈中弹出两个操作数进行运算，再压入栈中
3. 循环完毕后栈中剩下的最后一个元素就是答案

#include <iostream>
#include <cstdio>
#include <stack>
#include <vector>
#include <cstring>
using namespace std;
vector<string> rev;
bool prior(char a, char b){
    if((a == ‘+‘ || a == ‘-‘) && (b == ‘*‘ || b == ‘/‘))
        return false;
    else
        return true;
}
void pushOP(char a){
    char tmp[2];
    tmp[0] = a, tmp[1] = ‘\0‘;
    rev.push_back(string(tmp));
}
void reverseNotation(char* str){
    stack<char> op;
    for(int i=0; str[i] != ‘\0‘; i++){
        switch(str[i]){
            case ‘(‘:
                op.push(‘(‘);break;
            case ‘)‘:
                while(!op.empty()){
                    if(op.top()==‘(‘){
                        op.pop();
                        break;
                    }   
                    pushOP(op.top());
                    op.pop();
                }
                break;
            case ‘+‘:
            case ‘-‘:
            case ‘*‘:
            case ‘/‘:
                while(!op.empty() && op.top()!=‘(‘ && prior(op.top(),str[i])){
                    pushOP(op.top());
                    op.pop();
                }
                op.push(str[i]);
                break;
            default:
                char tmp[650]; int ptr = 0;
                while(str[i] <= ‘9‘ && str[i] >= ‘0‘){  
                    tmp[ptr++] = str[i++];
                }
                i--;
                tmp[ptr] = ‘\0‘;
                rev.push_back(string(tmp));
        }
    }
    while(!op.empty()){
        pushOP(op.top());
        op.pop();
    }
}
int solve(){
    stack<int>num;
    int size = rev.size();
    for(int i=0; i<size; i++){
        if(rev[i][0] <= ‘9‘ && rev[i][0] >= ‘0‘){
            num.push(atoi(rev[i].c_str()));
        }
        else{
            int n2 = num.top();
            num.pop();
            int n1 = num.top();
            num.pop();
            switch(rev[i][0]){
                case‘+‘:num.push(n1+n2);break;
                case‘-‘:num.push(n1-n2);break;
                case‘*‘:num.push(n1*n2);break;
                case‘/‘:num.push(n1/n2);break;
            }
        }
    }
    return num.top();
}
int main(){
    int n;
    cin>>n;
    cin.ignore();
    while(n--){
        rev.clear();
        char str[650]={};
        scanf("%s",str);
        reverseNotation(str);
        cout<<solve()<<endl;;
    }
}

参考：

Felix_Schmidt：poj 中缀表达式的值
aiyinju3323:数据结构与算法——编程作业——第三章 栈与队列

中缀表达式的值

原文：https://www.cnblogs.com/eneg/p/13911878.html