当前位置：首页 > news >正文

数据结构与算法——Java实现 24.中缀表达式转后缀

news 来源：原创 2024/9/29 1:50:52

目录

中缀表达式转后缀表达式

引言

思路

代码

正因为我有能力跨越，考验才会降临

—— 24.9.28

中缀表达式转后缀表达式

引言

Java中的编译器会将我们编写代码中的中缀表达式转化为后缀表达式，然后编译好输出程序

思路

遍历中缀表达式，如果遇上了变量，则将其加入后缀表达式中，如果遇上了符号，将其加入栈内，当再次遇到符号时遍历暂停，比较新符号与栈中符号的优先级，若新符号优先级大于旧符号，则新符号也入栈，若新符号优先级小于等于旧符号，则旧符号出栈进行运算，从栈中取出之前存入的符号与之前得到的字符进行运算

a+b ——> ab+

a*b+c ——> ab*c+

a+b*c ——> abc*+

a+b*c-d ——> abc*+d-

(a+b)*c ——> ab+c*

(a+b*c-d)*e ——> abc*+d-e*

a*(b+c) ——> abc+*

左括号直接入栈，左括号优先级设置为0

右括号就把栈里直到左括号为止的所有运算符出栈，左括号也出栈

遇到非运算符，直接拼接到串后

遇到+ - * /

① 若优先级高于栈顶运算符，入栈

② 若优先级低于栈顶运算符，将优先级 >= 栈内运算符都出栈进行运算，它再入栈

③ 遍历完成后，栈里剩余的运算符依次出栈，拼接到串尾部

代码

import java.util.LinkedList;public class InfixToSuffix {// 返回某符号的计算优先级static int priority(char c){return switch (c){case '*', '/' -> 2;case '+', '-' -> 1;case '(' -> 0;default -> throw new IllegalArgumentException("不合法的运算符");};}static String infixToSuffix(String exp){LinkedList<Character> stack = new LinkedList<>();// 用StringBuilder字符串拼接StringBuilder sb = new StringBuilder(exp.length());for (int i = 0; i < exp.length(); i++) {char c = exp.charAt(i);switch (c){case '+', '-', '*', '/' -> {if (stack.isEmpty()){stack.push(c);}else {if(priority(c) > priority(stack.peek())){stack.push(c);}else {while (!stack.isEmpty() && priority(stack.peek()) >= priority(c)){sb.append(stack.pop());}stack.push(c);}}}case '(' -> stack.push(c);case ')' -> {try {stack.pop();} catch (Exception e) {while (!stack.isEmpty() && stack.peek() != '('){sb.append(stack.pop());}stack.pop();}}default -> {sb.append(c);}}}while (!stack.isEmpty()){sb.append(stack.pop());}return sb.toString();}public static void main(String[] args) {System.out.println(infixToSuffix("a+b"));System.out.println(infixToSuffix("a+b-c"));System.out.println(infixToSuffix("a+b+c"));System.out.println(infixToSuffix("a*b+c"));System.out.println(infixToSuffix("a*b*c"));System.out.println(infixToSuffix("(a+b)*c"));System.out.println(infixToSuffix("a+b*c+(d*e+f)*g"));}
}