题目描述

表达式求值 有^,()
()会多余很迷，这个代码只有开头和结尾多余才会ac

样例

1+((1)+1 这样的算不了

算法1

(暴力枚举) $O(n)$

如何将中缀表达式变为前缀表达式？
建树然后线序遍历

时间复杂度

参考文献

视频题解

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)(j);i <= (int)(k);i ++)
#define debug(x) cerr<<#x<<":"<<(x)<<endl
#define fix cout<<fixed<<setprecision(20);
const int maxn=(int)1e6+5;

stack<int> num;
stack<char> op;
bool isnum(char c){return c>='0' and c<='9';}
int prior(char c){
    if(c=='(' )return 0;
    if(c=='+' or c=='-')return 1;
    if(c=='*' or c=='/')return 2;
    if(c=='^' )return 3;
    if(c==')' )return 4;
    return 0;
}
void cal(){
    //debug(1);
    int n2=num.top();num.pop();
    int n1=num.top();num.pop();

    char cc=op.top();op.pop();
   //debug(n1),debug(n2),debug(cc);
    if(cc=='+')n1+=n2;
    if(cc=='-')n1-=n2;
    if(cc=='*')n1*=n2;
    if(cc=='/')n1/=n2;
    if(cc=='^')n1=pow(n1,n2);
    //debug(n1);
    num.push(n1);
}
int main(){
    string s;cin>>s;
    s+=')';
    s='('+s;

    for(int i=0;i<s.size();i++){
        //debug(s[i]);
       // if(!num.empty())debug(num.top());
        char c=s[i];
        if(c>='0' and c<='9'  ){
            int cur=c-'0';
            while(isnum(s[i+1]))cur*=10,cur+=s[i+1]-'0',i++;
            num.push(cur);

        }
        else{
            //debug(c);
            if(c=='-' or c=='+'){
                if(c=='-'){
                    if(i>=1 and !(isnum(s[i-1]) or s[i-1]==')')){
                       // debug(s[i-1]),debug(s[i+1]);
                    i++;
                    int cur=s[i]-'0';
                    while(s[i+1]>='0' and s[i+1]<='9')cur*=10,cur+=s[i+1]-'0',i++;
                    num.push(-cur);
                     continue;
                    }

                }


                while(op.top()!='(') cal();
                op.push(c);


            }
            if(c=='/' or c=='*'){
                while(op.top()=='*' or op.top()=='/' or op.top()=='^')cal();
                op.push(c);
            }
            if(c=='^'){
                while(op.top()=='^')cal();
                op.push(c);
            }
            if(c=='(')op.push(c);
            if(c==')' and !op.empty()){
                //debug(op.top());

                while(op.top()!='(')cal();
                op.pop();
            }
        }

    }
    cout<<num.top();
}
//(2+2)^(1+1)
//((((7+9)^(1+3))
//((7+9)^(1+3))
//(3+5*4/2+2*(1+1)*(2+2))
/*
((1+1) 
(1))
wr 
多位数，
负号
 */