题解 | 表达式求值

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve (String s) {
        // write code here
       
        Stack<String> stack1 = new Stack<String>();
        Stack<Integer> stack2 = new Stack<Integer>();
        Map<String, Integer>  map = new HashMap<>();
        Queue<String> queue = new LinkedList<>();
        List<String> list =  new ArrayList<>();
        map.put("+", 1);
        map.put("-", 1);
        map.put("*", 2);
        map.put("(", 0);
        // map.put(")", 3);
        char[] a = s.toCharArray();
        for(int i=0;i<a.length;i++){
           if(a[i]>='0'&&a[i]<='9'){
              queue.add(a[i]+"");
           }else{
            String word ="";
            while(!queue.isEmpty()){
                word+=queue.poll();
            }
            if(!word.equals("")){
               list.add(word);
            }
              list.add(a[i]+"");
           }
        }
         String word ="";
        while(!queue.isEmpty()){
          word+=queue.poll();
        }
         if(!word.equals("")){
               list.add(word);
            }
        String[] b=new String[list.size()];
        for(int i=0;i<list.size();i++){
          b[i]=list.get(i);
        }
        for (int i = 0; i < b.length; i++) {
            if (map.containsKey(b[i])) {
                 if(b[i].equals("(")){
                  stack1.push(b[i]);
                  continue;
                }
               int value= map.get(b[i]);
               if(!stack1.isEmpty()){
                  int top = map.get(stack1.peek());
                  if (top > value&&!stack1.peek().equals("(")) {
                  while(map.get(stack1.peek())>value&&!stack1.peek().equals("(")){
                   int m= stack2.pop();
                   int n=stack2.pop();
                   String p= stack1.pop();
                   int val =count(n,m,p);
                   order(stack1,stack2,val);
                //    stack2.push(val);
                  }
                }
               }
                stack1.push(b[i]);
            }else{
                if(b[i].equals(")")){
                   while(!stack1.peek().equals("(")){
                    int m= stack2.pop();
                   int n=stack2.pop();
                   String p= stack1.pop();
                   int val =count(m,n,p);
                   stack2.push(val);
                   }
                   stack1.pop();
                }else{
                     order(stack1,stack2,Integer.parseInt(b[i]));
                    // stack2.push(Integer.parseInt(b[i]));
                }
            }
        }
        while(!stack1.isEmpty()){
                   int m= stack2.pop();
                   int n=stack2.pop();
                   String p= stack1.pop();
                   int val =count(m,n,p);
                    order(stack1,stack2,val);
                //    stack2.push(val);
        }
        return stack2.pop();
    }
    public static void order(Stack<String> stack1,Stack<Integer> stack2,int val){
       if(stack1.isEmpty()){
         stack2.push(val);
       }else{
         if(stack1.peek().equals("-")){
           stack1.pop();
           stack1.push("+");
           stack2.push(-val);
         }else{
            stack2.push(val);
         }
       }
    }
    public static int count(int n, int m, String p) {
        if (p.equals("*")) {
            return m * n;
        }
        if (p.equals("+")) {
            return m + n;
        } else {
            return m - n;
        }
    }
}

注意坑，+和*的位置可以互换，但是"-"的位置不能互换，3*4*5，3+4+5里面的任意一个数字位置都能互换,但是3-4-5就不能任意任意数的来换了。需要这个数入栈的时候需要看栈顶是否有“-”如果有需要把待加入的数换成相反数，再把“-”弹出，再入栈一个“+”；还有字符串拆解可以借助链表和队列；