题目描述

栈的应用，给定一个带括号和基本四运算符的表达式，输出其结果

样例

(2+2)*(1+1)

8

算法1

使用数组模拟栈操作

C++ 代码

#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;

const int N = 1e5+2;
int num[N];
char op[N];
int topn = -1, topo = -1;               //两个栈顶指针
unordered_map<char, int> prior{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'(', 0}};

void eval()
{
    int r = 0;
    int a = num[topn--];            //取栈顶元素赋值及pop操作；
    int b = num[topn--];
    char type = op[topo--];
    switch(type){
        case '+': r = b+a; break;
        case '-': r = b-a; break;
        case '*': r = b*a; break;
        case '/': r = b/a; break;
        default: break;
    }
    num[++topn] = r;
}//进行运算的函数；

int main()
{
    string s;
    cin>>s;
    for(int i = 0; i < s.size(); ++i){
        if(isdigit(s[i])){
            int x = 0, j = i;
            while(j < s.size() && isdigit(s[j])){           //是当数字超过一位数时的操作；
                x = x * 10 + s[j] - '0';
                ++j;
            }
            num[++topn] = x;
            i = j - 1;                                      //这里i=j-1是因为for循环的++i操作是在当前循环块完成之后进行的；
        }else if(s[i] == '(')
            op[++topo] = s[i];
        else if(s[i] == ')'){
            while(op[topo] != '(')
                eval();
            --topo;
        }//如果将topo--写进while循环里，则会出错，因为此时while会在判断时执行--操作然后再执行循环体；
        else{
            while(topo != -1 && prior[op[topo]] >= prior[s[i]])     //操作符优先级判断；
                eval();
            op[++topo] = s[i];
        }
    }
    while(topo != -1) eval();       //操作符栈不空就一直进行计算；
    cout<<num[topn]<<endl;
    return 0;
}