利用栈实现中缀表达式转后缀表达式，再利用栈对后缀表达式完成计算

虽然这个问题很简单...但确实困扰了我很久，感谢王道:D

 

 

代码如下：

#include <bits/stdc++.h>

using namespace std;
const int MAX=10005;
typedef struct node{
    bool flag;
    int data;
    char op;
}node;
typedef struct {
   int top;
   char buf[MAX];
}opStack;

typedef struct {
   int top;
   int buf[MAX];
}calcStack;
opStack stk1;
calcStack stk2;
char s[MAX];     //中缀表达式
node c[MAX];     //后缀表达式

int calc(int a,int b,char op){
    switch(op){
        case '+':return a+b;
        case '-':return a-b;
        case '*':return a*b;
        case '/':return a/b;
    }
    return -1;
}

bool check(char c){
    return c=='+'||c=='-'||c=='*'||c=='/';
}

bool compare(char a,char b){
    if(a=='+'||a=='-')
        return true;
    if(b=='*'||b=='/')
        return true;
    return false;

}

int main()
{
    scanf("%s",s);

    int index=0;
    bool flag=false;
    int temp=0;
    for(int i=0;s[i]!=0;i++){                   //中缀转后缀
        if(s[i]>='0'&&s[i]<='9'){
            flag=true;
            temp=temp*10+s[i]-'0';
        }else{
            if(flag){
                node cur;
                cur.flag=true;
                cur.data=temp;
                c[index++]=cur;
                temp=0;
                flag=false;
            }
            if(s[i]=='(')
                stk1.buf[stk1.top++]=s[i];
            else if(s[i]==')'){
                while(stk1.top>=1&&stk1.buf[stk1.top-1]!='('){
                    node cur;
                    cur.flag=false;
                    cur.op=stk1.buf[--stk1.top];
                    c[index++]=cur;
                }
                stk1.top--;
            }else{
                while(stk1.top>=1&&check(stk1.buf[stk1.top-1])&&compare(s[i],stk1.buf[stk1.top-1])){
                    node cur;
                    cur.flag=false;
                    cur.op=stk1.buf[--stk1.top];
                    c[index++]=cur;
                }
                stk1.buf[stk1.top++]=s[i];
            }
        }
    }
    if(flag){
        node cur;
        cur.flag=true;
        cur.data=temp;
        c[index++]=cur;
        temp=0;
        flag=false;
    }
    while(stk1.top>=1){
        node cur;
        cur.flag=false;
        cur.op=stk1.buf[--stk1.top];
        c[index++]=cur;
    }

    for(int i=0;i<index;i++){              //后缀计算
        if(c[i].flag){
            stk2.buf[stk2.top++]=c[i].data;
        }else{
            int right=stk2.buf[--stk2.top];
            int left=stk2.buf[--stk2.top];
            stk2.buf[stk2.top++]=calc(left,right,c[i].op);
        }
    }

    printf("%d\n",stk2.buf[stk2.top-1]);

    return 0;
}

 

再附上大一写的SB代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 10000000
typedef struct{
  int sum;
  int indexX;
  int indexY;
}node;
static char ans[N];
static int numX[N];
static char opeX[N];
static int topxX;
static int topyX;

int judge(char *ope,int y)
{
    if(y>1)
    {
        int ans1=0,ans2=0;
        if(ope[y-1]=='+'||ope[y-1]=='-')
            ans1=1;
        if(ope[y-1]=='*'||ope[y-1]=='/')
            ans1=2;
        if(ope[y-2]=='+'||ope[y-2]=='-')
            ans2=1;
        if(ope[y-2]=='*'||ope[y-2]=='/')
            ans2=2;
        if(ans1==ans2)
            return 1;
        else
            return ans1>ans2;
    }

    if(y<=0)
        return 0;

    return 1;
}

int sum(int a,int b,int x)
{
    int count;

    switch(x)
    {
        case '+':count=a+b; break;
        case '-':count=b-a; break;
        case '*':count=b*a; break;
        case '/':count=b/a; break;
    }

    return count;
}

int check(char* ope,int y)
{
    int ans1,ans2;

    if(y>1)
    {
        if(ope[y-1]=='*'&&ope[y-2]=='*')
            return 1;
        else
            return 0;
    }

    if(y==1)
        return 1;
    return 0;
}

node caculate(int *num,char *ope,int indexX,int indexY)
{
    node res;

    res.indexX=indexX-2;
    res.indexY=indexY-1;
    res.sum=sum(num[indexX-1],num[indexX-2],ope[indexY-1]);
    num[indexX-2]=res.sum;
    while(check(ope,indexY-1))
    {
        indexY--;
        indexX--;
        res.sum=sum(num[indexX-1],num[indexX-2],ope[indexY-1]);
        num[indexX-2]=res.sum;
        res.indexX=indexX-2;
        res.indexY=indexY-1;
    }

    return res;
}

int compute(int *num,char *ope,int topx,int topy)
{
    int count;

    while(topx>1)
    {
        if(judge(ope,topy))
        {
            int a=num[--topx];
            int b=num[topx-1];
            count=sum(a,b,ope[topy-1]);
            topy--;
            num[topx-1]=count;
        }
        else
        {
            node fuck=caculate(num,ope,topx-1,topy-1);
            int a=num[topx-1];
            num[fuck.indexX]=sum(a,fuck.sum,ope[topy-1]);
            topx=fuck.indexX+1;
            topy=fuck.indexY;
        }
    }

    return num[topx-1];
}

void transe()
{
    int i;
    int n=strlen(ans);
    int temp=0;
    int f=0;
    int x[N];                                      //多括号解决方法，在'（'起始调用calculate函数，返回node,直到')'为止，遇到'('继续调用
    char opt[N];
    int maxx=0;
    int maxy=0;
    int flag=0;

    for(i=0;i<n;i++)
    {
        if((ans[i]>='0'&&ans[i]<='9')||ans[i]=='+'||ans[i]=='/'||ans[i]=='*'||ans[i]=='-'||ans[i]==')'||ans[i]=='(')
        {
            if(ans[i]>='0'&&ans[i]<='9')
            {
                if(temp==0)
                    temp=ans[i]-'0';
                else
                    temp=temp*10+ans[i]-'0';
                if(i==n-1||ans[i+1]<'0'||ans[i+1]>'9')
                {
                    if(f==1)
                    {
                        numX[topxX++]=1/temp;
                        f=0;
                        if(flag)
                            x[maxx++]=1/temp;
                    }
                    else
                        if(f==2)
                        {
                            numX[topxX++]=-temp;
                            f=0;
                            if(flag)
                                x[maxx++]=-temp;
                        }
                    else
                    {
                        numX[topxX++]=temp;
                        if(flag)
                            x[maxx++]=temp;
                    }

                    temp=0;
                }
            }
            else
            {
                if(ans[i]=='(')
                    flag=1;
                else
                    if(ans[i]==')')
                    {
                        flag=0;
                        double change=compute(x,opt,maxx,maxy);
                        numX[topxX-maxx]=change;
                        topxX=topxX-maxx+1;
                        topyX-=maxy;
                        maxx=0;
                        maxy=0;
                    }
                 else
                    if(ans[i]=='/')
                    {
                        f=1;
                        opeX[topyX++]='*';
                        if(flag)
                            opt[maxy++]='*';
                    }
                else
                    if(ans[i]=='-')
                    {
                        f=2;
                        opeX[topyX++]='+';
                        if(flag)
                           opt[maxy++]='+';
                    }
                else
                {
                    opeX[topyX++]=ans[i];
                    if(flag)
                        opt[maxy++]=ans[i];
                }

            }
        }
    }
}

void test()
{

    gets(ans);
    transe();
    printf("%d\n",compute(numX,opeX,topxX,topyX));
}

int main()
{
    test();

    return 0;
}