题目描述
给出一个表达式,其中运算符仅包含+,-,*,/,^（加 减 乘 整除 乘方）要求求出表达式的最终值
数据可能会出现括号情况，还有可能出现多余括号情况
数据保证不会出现≥2……31的答案
数据可能会出现负数情况

题目就是这样简单明了，相信大家都能读懂，我也就不解释了，直接开干。

分析
看题目给的样例，这是一个中缀表达式，也是我们人类最熟悉的表达方式，但电脑它不熟悉呀，怎么办，那当然是把它转化成后缀表达式，那电脑算它不是有手就行。转化成后缀了又怎么办呢，那当然是用栈把它算出来啊。

思路有了，那怎么实现呢，首先我们要知道怎么实现上述转化
中缀表达式转后缀表达式
1.建立一个用于存运算符的栈，逐一扫描该中缀表达式中的元素
（1）如果遇到一个数，输出该数。
（2）如果遇到左括号，把左括号入栈。
（3）如果遇到右括号，不断取出栈顶并输出，直到栈顶为左括号，然后把左括号出栈
（4）如果遇到运算符，只要栈顶符号的优先级不低于新符号，就不断取出栈顶并输出，优先级为乘除>加减>左括号。
2.依次取出并输出栈中所有剩余符号，最后输出的表达式就是一个与原表达式等价的后缀表达式。
后缀表达式求值
1.建立一个用于存数的栈，逐一扫描该后缀表达式的每一个元素
（1）如果遇到一个数，则把该数入栈。
（2）如果遇到运算符，就把栈顶的两个数进行运算，把结果入栈。
2.扫描完成后，栈中恰好只剩一个数，就是该后缀表达式的值。

还有要特别注意的是可能有多余的括号。

理论都有了，直接上代码。

#include<bits/stdc++.h>
using namespace std;

const int N=110;
char s[N];//字符串 
char st[N];//存运算符 
char ans[N];//存数字 
int top,cnt,num;
int t[666];//标记运算符等级 
int stt[N];//计算结果的栈 

int chengfang(int a,int b)
{
    int k=1;
    while(b--)
        k*=a;
    return k;
}

signed main()
{
    t[int('^')]=4;//规定运算符等级 
    t[int('*')]=3;//
    t[int('/')]=3;//
    t[int('+')]=1;//
    t[int('-')]=1;//
    cin>>(s+1);//从第一位开始 
    int len=strlen(s+1);
    for(int i=1;i<=len;i++)
    {
        if(s[i]>='0'&&s[i]<='9')
            ans[++cnt]=s[i];
        else
        {
            if((s[i]=='-'&&i==1/*不要偷工减料*/)||(s[i-1]=='('&&s[i]=='-'))//当扫描的第一个数是负数，或者在字符串中间有负数 
            {
                ans[++cnt]='0';//就把负数转化为零减去这个数的绝对值 

                ans[++cnt]='#';
                st[++top]='-';//同时要加一个运算符 
                continue; 
            }


            if(s[i-1]>='0'&&s[i-1]<='9')//每读完一个数字就在后面加一个‘# ’隔开方便运算 
                ans[++cnt]='#';
            if(s[i]=='(')
                st[++top]=s[i];
            else if(s[i]==')')//当扫描到的是右括号，只要栈顶不是左括号就一直输出 
            {
                while(st[top]!='(')
                    ans[++cnt]=st[top--];
                top--;//栈顶指针后移 
            }
            else//为运算符 
            {
                while(t[s[i]]<=t[st[top]]&&top)//只要栈顶符号的优先级不低于新符号， 
                    ans[++cnt]=st[top--];        //就不断取出栈顶并输出
                st[++top]=s[i];//最后将新符号入栈 
            } 
        } 


    } 

    if(s[len]>='0'&&s[len]<='9')
        ans[++cnt]='#';
    while(top)//依次输出栈中所有剩余符号 
        ans[++cnt]=st[top--];             
    for(int i=1;i<=cnt;i++)
    {
        if(ans[i]>='0'&&ans[i]<='9')
        {
            num=num*10+ans[i]-'0';//转化为数字 
            continue;
        }
        if(ans[i]=='#')//扫描到了‘# ’ 
        {
            stt[++top]=num;
            num=0;//记得将num初始化，方便记录下一个数 
        }
        else//中缀转成后缀后 
        {
            top--;//每次遇到运算符就将栈顶的两个数进行运算，结果放回栈中 
            if(ans[i]=='+') 
                stt[top]=stt[top]+stt[top+1];
            else if(ans[i]=='-')
                stt[top]=stt[top]-stt[top+1];
            else if(ans[i]=='*')
                stt[top]=stt[top]*stt[top+1];
            else if(ans[i]=='/')
                stt[top]=stt[top]/stt[top+1];
            else if(ans[i]=='^')
                stt[top]=chengfang(stt[top],stt[top+1]);
            else top++;//特殊处理，如果遇到多余的括号，栈顶指针就不动 
        } 
    }
    cout<<stt[top]<<endl;
    return 0; 
}

这是本蒟蒻第一次写题解，希望能帮到像我一样的蒟蒻。
另外附上一份dalao的直接算中缀表达式的代码。

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
int num[260],topn=0,topo=0,g;
char st[260],ops[260];
int you(char ch){
    if(ch=='+'||ch=='-') return 2;
    if(ch=='*'||ch=='/') return 3;
    if(ch=='^') return 4;
    return 1;
}
inline int js(int a){
    int sum=0;
    int f=a;
    while(st[a]>='0'&&st[a]<='9')
        a++;
    g=a;
    for(int i=f;i<g;i++)
    sum=sum*10+(st[i]-'0');
    return sum;
}
inline void jia(){
    topo--;
    int sum=num[topn]+num[topn-1];
    topn--;
    num[topn]=sum;
}
inline void jian(){
    topo--;
    int sum=num[topn-1]-num[topn];
    topn--;
    num[topn]=sum;
}
inline void cheng(){
    topo--;
    int sum=num[topn-1]*num[topn];
    topn--;
    num[topn]=sum;
}
inline void chu(){
    topo--;
    int sum=num[topn-1]/num[topn];
    topn--;
    num[topn]=sum;
}
inline void mul(){
    topo--;
    int x = num[topn - 1], k = num[topn];
    int s = 1;
    for(int i = 1; i <= k; i ++ ) s *= x;    
    topn--;
    num[topn] = s;
}
int main(){
    gets(st);
    int len=strlen(st);
    st[len]=')';
    ops[++topo]='(';
    for(int i=0;i<=len;i++){
        if(st[i]>='0'&&st[i]<='9'){
                int x=js(i);i=g-1;
                num[++topn]=x;
               }
        else if(st[i]=='(')
                ops[++topo]='(';
        else if((st[i]=='-'&&i==0)||(st[i]=='-'&&st[i-1]=='(')){
                    num[++topn]=0;
                    ops[++topo]='-';
                }
        else if(st[i]=='+'||st[i]=='-'||st[i]=='*'||st[i]=='/'||st[i]=='^'){
                    while(you(ops[topo]) >= you(st[i])){
                        if(ops[topo]=='+') jia();
                        if(ops[topo]=='-') jian();
                        if(ops[topo]=='*') cheng();
                        if(ops[topo]=='/') chu();
                        if(ops[topo]=='^') mul();
                    }
                    ops[++topo]=st[i];
                }
        else if(st[i]==')'){
                    while(ops[topo]!='('){
                           if(ops[topo]=='+') jia();
                        if(ops[topo]=='-') jian();
                        if(ops[topo]=='*') cheng();
                        if(ops[topo]=='/') chu(); 
                        if(ops[topo]=='^') mul();
                    }
                    topo--;
                }     
    }
    printf("%d",num[topn]);
    return 0;
}