LeetCode刷题笔记day13-将普通表达式转化为逆波兰表达式_表达式转换成逆波兰式

将中缀表达式转换为逆波兰式，如“8+(4-2)×5+12/2”，转换为逆波兰式为8 4 2-5 × + 12 2 / +，利用栈这种数据结构，先模拟下详细过程：
①、首先遍历字符串数组，第一个数据为8，为数字，直接输出，故此时输出结果res为res = 8
②、此时遇到+号，非数字，且栈stack为空，则入栈，stack = +
③、遇到（，由于此时左括号优先级最高，故左括号入栈，此时stack = +（
④、遇到4，则直接输出此时res = 8 4
⑤、遇到-号，因为此时栈顶元素为（，故将+号优先级提升至最高，确保进栈（其实如果栈顶元素为(则运算符的优先级必须提至最高，确保进栈），此时stack = +（-
⑥、遇到2，则直接输出，此时res = 8 4 2
⑦、遇到）此时，将栈遍历输出栈中（之前的所有元素，并将左括号也出栈，此时stack = +，res = 8 4 2 -
⑧、遇到×，因为*的优先级比栈顶元素+高，所以×入栈，此时stack = + ×，res = 8 4 2 -
⑨、遇到5直接输出 res = 8 4 2 - 5
⑩、遇到 + 因为+的优先级比栈顶元素×低，故栈中所有元素出栈，若栈中存在（则（之前的元素出栈，并将这次遇到的+存入栈中，此时res = 8 4 2 - 5 × + ，stack = +
11、遇到 12 直接输出 此时 res = 8 4 2 - 5 × + 12
12、遇到 / 此时/ 优先级大于+故入栈，栈中元素为 stack = +/
13、遇到 2 直接输出 res = 8 4 2 - 5 × + 12 2
14、 遍历完所有元素后，则将栈中的剩余元素全部出栈，此时stack = null
res = 8 4 2 - 5 × + 12 2 / +
结束！！！

class Solution {
    public int getNum() {
      String[] s = {"8","+","(","4","-","2",")","*","5","+","12","/","2"};
      Stack<String> st = new Stack();
      int  index = 0;
      while(index<s.length){
          //数字直接输出
          if(isDigit(s[index])){
              System.out.print(s[index]+"");
          }
          else{
              if(s[index].equals(")")){
                  while(!st.isEmpty() && !st.peek().equals("(")){
                      System.out.print(st.pop()+"");
                  }
                  if(!st.isEmpty()){
                        st.pop();
                  }
              }
              else if(st.isEmpty() || priority(s[index],st)>=priority(st.peek(),st)){
                  st.push(s[index]);
              }
              else{
                  while(!st.isEmpty() && !st.peek().equals("(")){
                  System.out.print(st.pop()+"");
                  }
                    st.push(s[index]);
              }
          }
           index++;
      }
      while(!st.isEmpty()){
          System.out.print(st.pop()+"");
      }
      return 1;
    }
    public int priority(String c,Stack st){
           switch(c){
               case"+":
               case"-": 
               while(st.peek().equals("("))
               return 4;
               return 1;
               case"*":
               case"/": return 2;
               case"(":
               case")":return 3;
               default: return 0;
           }
    }
    public boolean isDigit(String s){
        switch(s){
            case "+":
            case "-":
            case "*":
            case "/":
            case "(":
            case ")":
            return false;
            default:
            return true;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64