题解 | #表达式求值#

//中缀表达式求和，懒得写注释了，就是数据结构书上的栗子，不会的同学自行复习
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int solve(string s) {
        // write code here
        int stack1[100],top1=-1,top2=-1;
        char stack2[100];
        int sum=0;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]>='0'&&s[i]<='9')
                sum=sum*10+s[i]-'0';
            else{
                if(sum!=0)
                {
                    stack1[++top1]=sum;
                    sum=0;
                }
                if(top2==-1||judge(s[i],stack2[top2])==true)
                    stack2[++top2]=s[i];
                else{
                    if(s[i]==')')
                    {
                        while(stack2[top2]!='(')
                        {
                            char ch=stack2[top2--];
                            int x=stack1[top1--];
                            int y=stack1[top1--];
                            if(ch=='+')
                                stack1[++top1]=x+y;
                            else if(ch=='-')
                                stack1[++top1]=y-x;
                            else if(ch=='*')
                                stack1[++top1]=x*y;
                            else stack1[++top1]=y/x;
                        }
                        top2--;
                    }
                    else{
                        while(top2!=-1&&judge(s[i],stack2[top2])==false)
                        {
                            char ch=stack2[top2--];
                            int x=stack1[top1--];
                            int y=stack1[top1--];
                            if(ch=='+')
                                stack1[++top1]=x+y;
                            else if(ch=='-')
                                stack1[++top1]=y-x;
                            else if(ch=='*')
                                stack1[++top1]=x*y;
                            else stack1[++top1]=y/x;
                        }
                        stack2[++top2]=s[i];
                    }
                }
            }
        }
        if(sum!=0)
            stack1[++top1]=sum;
        char ch=stack2[top2--];
        int x=stack1[top1--];
        int y=stack1[top1--];
                            if(ch=='+')
                                return x+y;
                            else if(ch=='-')
                                return y-x;
                            else if(ch=='*')
                               return x*y;
                       return y/x;
    }
    bool judge(char c1,char c2)
    {
        if(c1=='(')
            return true;
        else if(c1==')')
            return false;
        else if(c2=='(')
            return true;
        else if((c1=='*'||c1=='/')&&(c2=='+'||c2=='-'))
            return true;
        else return false;
    }
};