Description

输入一个只包含+,-,*,(,）的数字运算式（中缀表达式），求出他的计算结果。

例如，输入5*(7-3)+9，输出29

Input

一个中缀表达式。

Output

表达式的计算结果。

Sample Input

5*（7-3）+9

 

Sample Output

29

 

Hint

输入的表达式的长度不超过100，最终结果和中间结果不会超过integer

保证输入的字符串一定是一个中缀表达式，不需要检测错误！

Source

 

 

做法：先把表达式转换成中缀表达式。

        逐个压入栈中，遇到符号弹出2个。

 

 

很短的代码：

 

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

char s[201],op[201],q[201];

long a[201];

long i,j,k;

int fun(){

    gets(s);

    j=-1;

    for (i=0;i<strlen(s);i++){

        if (s[i]=='(')

             q[++k]='(';

        else if (s[i]==')'){

             while (q[k]!='('){

                 op[++j]=q[k--];

             }

             k--;

        }else if (s[i]=='+' || s[i]=='-'){

            while(k>=0 && q[k]!='(')

                op[++j]=q[k--];

            q[++k]=' ';

            q[++k]=s[i];

        }else if (s[i]=='*'){

            while(k>=0 && q[k]!='(' && q[k]!='+' && q[k]!='-')

                op[++j]=q[k--];

            q[++k]=' ';

            q[++k]=s[i];

        }else{

            op[++j]=s[i];

            if(i==strlen(s)-1)

                op[++j]=' ';

            else if (s[i+1]>'9' || s[i+1]<'0')

                op[++j]=' ';

        }

    }

    while (k>=0)

        op[++j]=q[k--];

    op[++j]='\0';

    return j;

}

int main(){

    int p=0,o=0,i,k,j;

    j=fun();

    for (i=0;i<j;){

        if (op[i]<='9' && op[i]>='0'){

            k=0;

            p++;

            while (op[i]<='9' && op[i]>='0'){

                k=k*10+op[i]-48;

                i++;

            }

            a[p]=k;

        }else if (op[i]=='+'){

            a[p-1]=a[p-1]+a[p];

            p--;

            i++;

        }else if (op[i]=='-'){

            a[p-1]=a[p-1]-a[p];

            p--;

            i++;

        }else if (op[i]=='*'){

            a[p-1]=a[p-1]*a[p];

            p--;

            i++;

        }else i++;

    }

    printf("%ld\n",a[1]);

    return 0;

}