中缀表达式：a+b*c
后缀表达式：abc*+

解题思路：栈

首先假设我们需要转化的中缀表达式为：
image.png

  1. 从左到右扫描每一个字符。如果扫描到的字符是 操作数 ，就直接输出这些操作数。
  2. 如果扫描到的字符是一个操作符，分三种情况：
    • 如果栈空或者栈顶元素为 “ ( “，直接将操作符存储到栈中（push it）
    • 栈非空但该操作符的优先级大于栈顶的操作符，就直接将操作符存储到栈中（push it）
    • 栈非空但该操作符的优先级不大于栈顶的操作符，就将栈顶的操作符出栈（pop it）,直到该操作符的优先级大于栈顶的操作符或者左括号或者栈空。将扫描到的操作符存储到栈中（push it）。

image.png
image.png
image.png

  1. 如果遇到的操作符是左括号“（ “，直接将该操作符存储到栈中。该操作符只有在遇到右括号“ ) “的时候移除。这是一个特殊符号该特殊处理。

    image.png
    image.png
    image.png

  2. 如果扫描到的操作符是右括号“ ）”，将栈中的操作符全部导出（pop it），直到遇见左括号“（ “。将栈中的左括号移出栈（pop it ）。继续扫描下一个字符 。

    image.png

  3. 如果输入的中缀表达式已经扫描完，但栈中仍存在操作符，此时将栈中的操作符全部导出到output 中

    1.      ![image.png](https://cdn.nlark.com/yuque/0/2021/png/2955945/1635059333835-1a2b0be3-3afb-46ad-8139-863dde81de7b.png#clientId=ud19a7240-e26a-4&from=paste&height=154&id=u985695b7&margin=%5Bobject%20Object%5D&name=image.png&originHeight=308&originWidth=1229&originalType=binary&ratio=1&size=102072&status=done&style=stroke&taskId=u0a607e7c-2359-42e4-accc-9ec800f4e39&width=614.5)

我的代码

遇到的小BUG：判断字符串请使用 equals() 而不是简单的 ==

  1. public class Solution {
  2.     //#中缀转后缀
  3.     public static String[]  MidToLRPN(String[] tokens) {
  4.         List<String>ans=new ArrayList<>();
  5.         Stack<String> stack=new Stack<>();
  6.         //利用map快速匹配优先级
  7.         Map<String,Integer> PriorityOp=new HashMap<>();
  8.         PriorityOp.put("+",1); PriorityOp.put("-",1);
  9.         PriorityOp.put("*",2); PriorityOp.put("/",2);
  10.         for(String token:tokens){
  11.             switch (token){
  12.                 //括号部分
  13.                 case "(":
  14.                     stack.add(token);   //遇到( ,直接入栈
  15.                     break;
  16.                 case ")":
  17.                     while(!stack.peek().equals("(")) ans.add(stack.pop()); //将出栈至遇到(
  18.                     stack.pop();       //出栈 (
  19.                     break;
  20.                 //操作符部分
  21.                 case "+":
  22.                 case "-":
  23.                 case "*":
  24.                 case "/":
  25.                     if(stack.isEmpty()||stack.peek().equals("("))    //栈空或者栈中只有( 入栈
  26.                         stack.add(token);
  27.                     else if(PriorityOp.get(token)>PriorityOp.get(stack.peek())){
  28.                         stack.add(token);        //栈非空,操作符优先级高于栈内元素,入栈
  29.                     }else {
  30.                         //判断顺序不可改变
  31.                         while(!stack.isEmpty()&&!stack.peek().equals("(")&&PriorityOp.get(token)<=PriorityOp.get(stack.peek())){
  32.                             ans.add(stack.pop());  //栈非空,出栈至栈空||栈顶为(||优先级大于栈顶
  33.                         }
  34.                         stack.add(token);          //自身入栈
  35.                     }
  36.                     break;
  37.                 //数字部分:
  38.                 default:
  39.                     ans.add(token);
  40.                     break;
  41.             }
  42.         }
  43.         //表达式遍历完成,将栈剩余元素导出至 ans 中
  44.         while(!stack.isEmpty()) ans.add(stack.pop());
  45.         return ans.stream().toArray(String[]::new);
  46.     }
  47. }