题目描述

给出一个表达式,其中运算符仅包含

+,-,*,/,^
（加 减 乘 整除 乘方）要求求出表达式的最终值。

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

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

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

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

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

样例

输入样例：
(2+2)^(1+1)
输出样例：
16

中缀表达式转后缀表达式

题目数据还是比较水没有考虑负指数还有负负得正的情况就水过了…括号的是真的坑人,需要先特判一下把多余的括号删除掉,然后就是开头负数自己添加上(0-…),还有就是两位数的情况直接把他们都拆开划分为空格然后stringstream模拟

真实酸爽题还好可以看错误数据

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int qpow(int a,int b)
{
    int ans=1;
    for(int i=1;i<=b;i++)
    ans*=a;
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    stack<char> st;
    string s,t="";
    cin>>s;
    stack<int> ck;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='(')
        ck.push(i);
        else if(s[i]==')')
        {
            if(ck.size())
            ck.pop();
            else
            ck.push(i);
        }
    }
    while(ck.size())
    {
        s.erase(ck.top(),1);
        ck.pop();
    }
    for(int i=s.size()-1;i>=0;i--)
    if(s[i]=='-'&&((!isdigit(s[i-1])&&s[i-1]!=')'&&s[i-1]!=')')||i==0))
    {
      for(int j=i+1;j<s.size();j++)
      if(!isdigit(s[j])||j==s.size()-1)
      {
        if(j==s.size()-1)
        s.insert(j+1,")");
        else
        s.insert(j,")");
        s.insert(i,"(0");
        break;
      }
    }
    for(int i=0;i<s.size();i++)
    {
        if(isdigit(s[i]))
        {
          t+=s[i];
          if(!isdigit(s[i+1]))
          t+=' ';
        }
        else if(s[i]=='(')
        st.push(s[i]);
        else if(s[i]==')')
        {
            while(st.top()!='(')
            {
                t+=st.top();
                t+=' ';
                st.pop();
            }
            st.pop();
        }
        else
        {
            if(s[i]=='+'||s[i]=='-')
            {
                while(st.size()&&(st.top()=='+'||st.top()=='-'||st.top()=='*'||st.top()=='/'||st.top()=='^'))
                {
                    t+=st.top();
                    t+=' ';
                    st.pop();
                }
                st.push(s[i]);
            }
            if(s[i]=='*'||s[i]=='/')
            {
                while(st.size()&&(st.top()=='*'||st.top()=='/'||st.top()=='^'))
                {
                    t+=st.top();
                    t+=' ';
                    st.pop();
                }
                st.push(s[i]);
            }
            if(s[i]=='^')
            {
                while(st.size()&&(st.top()=='^'))
                {
                    t+=st.top();
                    t+=' ';
                    st.pop();
                }
                st.push(s[i]);
            }
        }
    }
    while(st.size())
    {
        t+=st.top();
        t+=' ';
        st.pop();
    }
    stack<int> sum;
    stringstream x;
    x<<t;
    string te;
    while(x>>te)
    {
      string tee="";
      if(isdigit(te[0]))
      {
        for(int i=0;i<te.size();i++)
        tee+=te[i];
        stringstream tr;
        tr<<tee;
        int ssum;
        tr>>ssum;
        sum.push(ssum);
      }
      else
      {
        int t1=sum.top();
        sum.pop();
        int t2=sum.top();
        sum.pop();
        if(te[0]=='+')
        sum.push(t1+t2);
        else if(te[0]=='-')
        sum.push(t2-t1);
        else if(te[0]=='*')
        sum.push(t2*t1);
        else if(te[0]=='/')
        sum.push(t2/t1);
        else if(te[0]=='^')
        sum.push(qpow(t2,t1));
      }
    }
    cout<<sum.top();
}