java - 中缀表达式转后缀表达式

思路分析：
1、初始化两个栈：运算符栈s1、储存中间结果的栈s2
2、从左至右扫描中缀表达式
3、遇到操作数时，将其压入s2
4、遇到运算符时，比较其与s1栈顶运算符的优先级
    1）如果s1为空，或栈顶运算符为左括号"("，则直接将运算符入栈
    2）如果s1不为空
        a、若优先级比栈顶优先级高，也将运算符入栈
        b、否则，将s1栈顶的运算符弹出并压入到s2中，再次转到4、1与s1中新的栈顶运算符相比较
5、遇到括号时：
    1）如果是左括号"("，直接压入s1
    2）如果是右括号")"，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
6、重复步骤2-5，直到表达式的最右边
7、将s1中剩余的运算符依次弹出并压入s2
8、依次弹出s2中的元素并输出，结果的 逆序 即为中缀表达式对应的后缀表达式

public class PolandNotation {

  public static void main(String[] args) {
    
    // 将中缀表达式转成后缀表达式
    // 1+((2+3)*4)-5  -->  1 2 3 + 4 * + 5 -
    // 因为直接对字符串进行操作不方便，因此，先将中缀表达式字符串转为中缀表达式对应的List
    // 即 1+((2+3)*4)-5  -->  ArrayList [1,+,(,(,2,+,3,),*,4,),-,5,]
    
    // 定义中缀表达式
    String expression = "1+((2+3)*4)-5";
    List infixexpressionList = toInfixexpressionList(expression);
    System.out.println("中缀表达式list：" + infixexpressionList);
    
    List parseSuffixExpreesionList = parseSuffixExpreesionList(infixexpressionList);
    System.out.println("后缀表达式list：" + parseSuffixExpreesionList);
    
    
  }
  
  
  // 中缀表达式对应的list -> 后缀表达式对应的list
  // ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] -> ArrayList [1,2,3,+,4,*,+,5,–]
  public static List parseSuffixExpreesionList(List ls){
    // 定义2个栈
    Stack s1 = new Stack();   // 符号栈
    // 说明：因为s2这个栈，在整个转换过程中没有pop操作，而且如果使用栈这个数据结构，后面还需要逆序输出，比较麻烦，因此在这里使用List，直接输出即为栈的逆序输出
    List s2 = new ArrayList();
    
    // 遍历ls
    for(String item: ls) {
      // 如果是一个数，加入s2
      if(item.matches("\d+")) {
        s2.add(item);
      }else if(item.equals("(")) {
        // 如果是左括号，加入s1符号栈
        s1.push(item);
      }else if(item.equals(")")) {
        // 如果是）括号，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
        while(!s1.peek().equals("(")) {
          s2.add(s1.pop());
        }
        // 将(弹出s1栈，消除小括号
        s1.pop();
      }else {
        // 当item的优先级小于等于s1栈顶运算符，将s1栈顶的运算符弹出并加入到s2中
        while(s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
          s2.add(s1.pop());
        }
        // 还需要将item压入栈
        s1.push(item);
      }
    }
    
    // 将s1中剩余运算符依次弹出并加入s2
    while(s1.size() != 0) {
      s2.add(s1.pop());
    }
    
    // 注意因为是存放到List，因此按顺序输出就是对应的后缀表达式对应的list
    return s2;
  }
  
  
  
  // 将中缀表达式转换为对应的list
  public static List toInfixexpressionList(String s){
    // 定义一个list，存放中缀表达式
    List ls = new ArrayList();
    // 定义一个指针，用于遍历中缀表达式字符串
    int i = 0;
    // 用于对多位数拼接
    String str;
    // 每遍历到一个字母，就存放到c
    char c;
    do {
      // 如果c是一个非数字，直接加入到ls中
      // charAt(i)：获取字符串中i位置的字符，i从0开始
      // SACII码   48 - 57   --->   0 - 9
      if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) >57 ) {
        ls.add(String.valueOf(c));
        i++;
      } else { // 如果是数，需要考虑多位数
        // 置空
        str = "";
        while(i < s.length() && (c = s.charAt(i))>=48 && (c = s.charAt(i))<=57) {
          str += c;
          i++;
        }
        ls.add(str);
      }
    }while(i < s.length());
    return ls;
  }
  
}


// 编写一个Operation类，返回运算符对应的优先级
class Operation{
  private static int ADD = 1;
  private static int SUB = 1;
  private static int MUL = 2;
  private static int DIV = 2;
  
  public static int getValue(String operation) {
    int result = 0;
    switch (operation) {
    case "+":
      result = ADD;
      break;
    case "-":
      result = SUB;
      break;
    case "*":
      result = MUL;
      break;
    case "/":
      result = DIV;
      break;
    default:
      break;
    }
    return result;
  }
}