LeetCode772—基本计算器III

栈 队列

第一次提交的代码：（栈+递归）

class Solution {
    public int nw=0;
    public int calculate(String s) 
    {
      return cal(s);
    }
    private int cal(String s)//自递归函数多用private
    {
      Stack<Integer> stack=new Stack<>();//泛型定义的new中不用再写一次泛型名
      int w=0;
      char op='+';
      for(;nw<s.length();nw++)
      {
         char c=s.charAt(nw);
         if(Character.isDigit(c)) w=w*10+c-'0';//高级的Character.isDigit()函数
         if(c=='(')//左括号标志着局部问题的开始，递归！
         {
            nw++;
            w=cal(s);
         }
        //当遇到了新的运算符，就要对上一个运算符op和累计的数字num作运算
         if((!Character.isDigit(c)&&c!=' ')||nw==s.length()-1)
         //空格直接无视；遇到字符串末尾，肯定是要结算的
         {
            int t=0;
            switch(op)
            {
                case '+':stack.push(w);break;
                case '-':stack.push(-w);break;
                case '*':t=stack.pop();stack.push(t*w);break;
                case '/':t=stack.pop();stack.push(t/w);break;
            } 
            op=c;
            w=0;
         }
         if(c==')') break;//右括号标志着局部问题的结束，退出！
      }
      int ans=0;
      //结果汇总
      while(!stack.isEmpty())
      {
        ans+=stack.pop();
      }
      return ans;
    }
}

第二次提交的代码：（栈+后缀表达式）

class Solution {
    public String posts="";
    public int calculate(String s)
    {
        Trans(s);
        return getValue();
    }
    public void Trans(String s)//将中缀表达式转化为后缀表达式的函数
    {
        Stack<Character> stack=new Stack<>();
        int i=0,n=s.length();
        char ch;
        while(i<n)
        {
            ch=s.charAt(i);
            if(ch=='(') stack.push(ch);
            if(ch==')') 
            {
                while(!stack.empty()&&stack.peek()!='(')
                {
                    posts+=stack.pop();
                }
                stack.pop();//将（退栈
            }
            if(ch=='+'||ch=='-')
            {
                while(!stack.empty()&&stack.peek()!='(')
                {
                    posts+=stack.pop();//将不低于ch的所有运算符退栈
                }
                stack.push(ch);
            }
            if(ch=='*'||ch=='/')
            {
                while(!stack.empty()&&stack.peek()!='('&&(stack.peek()=='*'||stack.peek()=='/'))
                {
                    posts+=stack.pop();//将不低于ch的所有运算符退栈
                }
                stack.push(ch);
            }
            if(Character.isDigit(ch))//Character.isDigit()是判断ch是否为数字的内置函数
            {
                while(Character.isDigit(ch))//一次把数字读完
                {
                    posts+=ch;
                    i++;
                    if(i<n) ch=s.charAt(i);
                    else break;
                }
                i--;//前面i多右移了一位
                posts+='#';//标识着一个数字的结束（要不然两个数字会连在一次，被当成一个数字。。。）
            }
            i++;
        }
        while(!stack.empty())//最后记得把栈清空
        {
            posts+=stack.pop();
        }
    }
    public int getValue()//求后缀表达式的值
    {
        Stack<Integer> S=new Stack<>();
        int i=0,n=posts.length();
        int a,b;
        char ch;
        while(i<n)
        {
            ch=posts.charAt(i);
            switch(ch)
            {
                case '+':a=S.pop();b=S.pop();S.push(b+a);break;
                case '-':a=S.pop();b=S.pop();S.push(b-a);break;
                case '*':a=S.pop();b=S.pop();S.push(b*a);break;
                case '/':a=S.pop();b=S.pop();S.push(b/a);break;
                default:
                    int w=0;
                    while(Character.isDigit(ch))
                    {
                        w=w*10+ch-'0';
                        i++;
                        if(i<n) ch=posts.charAt(i);//读取数组元素时小心越界问题
                        else break;
                    }
                    //由于有#，就不需要再回退了
                    S.push(w);
                    break;
            }
            i++;
        }
        return S.peek();
    }
}