可以ac

题目描述

给出一个表达式,其中运算符仅包含+,-,*,/,^（加 减 乘 整除 乘方）要求求出表达式的最终值。

数据可能会出现括号情况，还有可能出现多余括号情况。

数据保证不会出现大于或等于231
的答案。

数据可能会出现负数情况。

数据保证不会出现指数为负数的情况。

输入格式
输入仅一行，即为表达式。

输出格式
输出仅一行，既为表达式算出的结果。

样例

输入样例：

(2+2)^(1+1)

输出样例：

16

#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>
#include<unordered_map>

using namespace std;

stack<int> num;
stack<char> ops;

void eval()
{
    int b = num.top(); num.pop();
    int a = num.top(); num.pop();
    char c = ops.top(); ops.pop();
    int x = 1;
    if(c == '+') x = a + b;
    else if(c == '-') x = a - b;
    else if(c == '*') x =  a * b;
    else if(c == '/') x = a / b;
    else{
        while(b -- )
            x = x * a;
    }
    // cout << "x = " << x << endl;
    num.push(x);
}

int main()
{
    string str;
    cin >> str;

    unordered_map<char, int> pr;
    pr['+'] = pr['-'] = 1;
    pr['*'] = pr['/'] = 2;
    pr['^'] = 3;

    // 1. 多余括号的情况，要么左括号多余，要么右括号多余
    // 其实左括号多余不需要管，入栈不处理就行，最后会剩到栈里面。当右括号多余的时候不行，为什么
    // 逻辑上当发现右括号的时候，需要计算括号中所有表达式的值，如果找不到相匹配的左括号，就计算完了本不应该计算的值
    // 例：2 * (5 + 6)) ^ 2 多了一个右括号，本应该先计算(5 + 6)的平方，但是当读到多余的右括号的时候，找不到前面对应的左括号
    // 就会先计算完2 * 11再计算平方，答案错误
    // 这里不好解决，出题有歧义，自己的想法：先读一遍去除多余括号，然后再进行计算。

    // 这道题的只考虑的是左边括号多余和最后面右括号多余的情况。例如： 2 * ((5 + 6) + 3))))，最后读到右括号，没有了匹配的左括号，代码无法继续。
    // 2. 技巧: 在表达式左右加一对括号，可以保证最后计算完，栈顶剩余的那个元素就是结果

    string left, right;
    for(int i = 0; i < str.size(); i++ ) left+='(';
    for(int i = 0; i < str.size(); i++ ) right+=')';
    str = "((((((((((((((" + left + str + "))))))))))))))";

    /*
        1. 读到左括号和数字直接压栈（注意读入数据时判断正负号后压栈再删除读入的减号就导致当读入'-'时无法判断是负号还是减号）
        2. 读到加减乘除，则判断当前运算符和栈顶元素的优先级，当前元素的优先级<=栈顶元素的优先级，就计算前面的的两个元素值
        3. 读到右括号，则计算元素直到读到'('，需要注意的是计算的时候，是不需要注意优先级的，因为前面的操作已经让操作符优先级
           从小到大排列了，逆序或者相等的优先级符号都已经被计算了，所以无需考虑
     */

    for(int i = 0; i < str.size(); i ++)
    {
        char c = str[i];
        if(c <= '9' && c >= '0'){
            // 数据可能大于9
            int j = i, t = 0;
            while(str[j] <= '9' && str[j] >= '0')
            {
                t = t * 10 + str[j] - '0';
                j ++;
            }
            num.push(t);
            i = j - 1;
        }else if(c == '-'){  // 读入'-'时要判断是减号还是负号
            if(i == 0 || ( (str[i - 1] < '0' || str[i - 1] > '9') && str[i - 1] != ')' ) )
            {
                if(str[i - 1] == '(' && str[i + 1] == '(')
                {
                    num.push(0);
                    ops.push(c);
                }else
                {
                    int j = i + 1, t = 0;
                while(str[j] >= '0' && str[j] <= '9')
                {
                    t = t * 10 + str[j] - '0';
                    j ++;
                }
                num.push(-t);
                i = j - 1;
                }
            }
            else
            {
                if(ops.size() && pr[c] <= pr[ops.top()]) eval();
                ops.push(c);
            } 
        }else if(c == ')'){
            while(ops.top() != '(')
            {
                eval();
            }
            ops.pop();
        }
        else if(c == '(')  // 多加了左括号，((2 当读入第二个左括号时，栈内和当前符号优先级相同，会执行eval()，所以要单独处理左括号
        {
            ops.push(c);
        }
        else{
            if(ops.size() && pr[c] <= pr[ops.top()]) 
            {
                eval();
            }
            ops.push(c);
        }
        // if(ops.size() && num.size())
        //     cout << "栈顶元素： " << ops.top() << " " << num.top() << endl;
    }

    cout << num.top() << endl;

    return 0;
}