中缀表达式转换为后缀表达式（Java）
博客说明
文章所涉及的资料来自互联网整理和个人总结，意在于个人学习和经验汇总，如有什么地方侵权，请联系本人删除，谢谢！
步骤
- 初始化两个栈:运算符栈 s1 和储存中间结果的栈 s2
- 从左至右扫描中缀表达式
- 遇到操作数时，将其压 s2
遇到运算符时，比较其与 s1 栈顶运算符的优先级:
- 如果 s1 为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈
- 否则，若优先级比栈顶运算符的高，也将运算符压入 s1;
- 否则，将 s1 栈顶的运算符弹出并压入到 s2 中，再次转到(4-1)与 s1 中新的栈顶运算符相比较;
遇到括号时:
- 如果是左括号“(”，则直接压入 s1
- 如果是右括号“)”，则依次弹出 s1 栈顶的运算符，并压入 s2，直到遇到左括号为止，此时将这一对括号丢弃
- 重复步骤 2 至 5，直到表达式的最右边
- 将 s1 中剩余的运算符依次弹出并压入 s2
- 依次弹出 s2 中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
案例
将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下
因此结果为 :"123+4 × +5 –"
代码
package stack;import java.util.ArrayList;import java.util.List;import java.util.Stack;/** * @author guizimo * @date 2020/4/6 12:25 下午 */public class PolandNotation { public static void main(String[] args) { //表达式 String suffixExpression = "1+((2+3)*4)-5"; //中缀表达式对应的List System.out.println("中缀表达式对应的List"); List<String> infixExpressionList = toInfixExpressionList(suffixExpression); System.out.println(infixExpressionList); //后缀表达式对应的List System.out.println("后缀表达式对应的List"); List<String> suffixExpressionList = parseSuffixExpressionList(infixExpressionList); System.out.println(suffixExpressionList); //计算逆波兰表达式 System.out.printf("suffixExpression=%d", calculate(suffixExpressionList)); } public static List<String> parseSuffixExpressionList(List<String> ls) { //定义两个栈 Stack<String> s1 = new Stack<String>(); //符号栈 List<String> s2 = new ArrayList<String>(); //结果 for (String item : ls) { //如果是一个数 if (item.matches("\\d+")) { s2.add(item); } else if (item.equals("(")) { s1.push(item); } else if (item.equals(")")) { while (!s1.peek().equals("(")) { s2.add(s1.pop()); } s1.pop(); } else { while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) { s2.add(s1.pop()); } s1.push(item); } } while (s1.size() != 0) { s2.add(s1.pop()); } return s2; } //将中缀表达式转换成list public static List<String> toInfixExpressionList(String s) { List<String> ls = new ArrayList<String>(); int i = 0; String str; //多位数 char c; do { //非数字 if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) { ls.add("" + 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; } //完成对逆波兰表达式的计算 public static int calculate(List<String> ls) { Stack<String> stack = new Stack<>(); for (String item : ls) { //使用正则表达式 if (item.matches("\\d+")) { //匹配多位数 //入栈 stack.push(item); } else { int num2 = Integer.parseInt(stack.pop()); int num1 = Integer.parseInt(stack.pop()); int res = 0; if (item.equals("+")) { res = num1 + num2; } else if (item.equals("-")) { res = num1 - num2; } else if (item.equals("*")) { res = num1 * num2; } else if (item.equals("/")) { res = num1 / num2; } else { throw new RuntimeException("运算符有问题"); } //把结果入栈 stack.push("" + res); } } return Integer.parseInt(stack.pop()); }}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: System.out.println("不存在"); break; } return result; }}感谢
尚硅谷万能的网络
以及勤劳的自己