逆波兰算法、中缀表达式转后缀表达式
2022/3/19 12:57:45
本文主要是介绍逆波兰算法、中缀表达式转后缀表达式,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一、前、中、后缀表达
前缀表达式(波兰表达式、Prefix expression)
又称为波兰表达式,前缀表达式的运算符位于操作数之前
例如:(3 + 4) * 5 - 6对应的前缀表达式:- * + 3 4 5 6
中缀表达式(Infix expression)
中缀表达式就是常见的运算表达式,中缀表达式的求值往往是人们所熟悉的,但是对计算机来说却不好操作,一般将中缀表达式转换成其他表达式(一般转换成后缀表达式)
例如:(3 + 4) * 5 - 6
后缀表达式(逆波兰表达式、Postfix expression)
又称逆波兰表达式,后缀表达式的运算符位于操作数之后
例如:(3 + 4) * 5 - 6对应的后缀表达式为:3 4 + 5 * 6 -
二、中缀表达式转前、后缀表达式(手算)
转换过程
中缀表达式为:a + b * c - ( d + e )
- 使用按照运算符的优先级对所有的运算单位加括号
操作完成后式子变成:( ( a + ( b * c ) ) - ( d + e ) )
- 中缀表达式转前缀表达式:
1)将运算符移动到对应括号之前:- ( + ( a * ( b c ) ) + ( d e ) )
2)去掉括号:- + a * b c + d e
3)转换完成 - 中缀表达式转后缀表达式:
1)将运算符移动到对应括号之后:( ( a ( b c ) * ) + ( d e ) + ) -
2)去掉括号:a b c * + d e + -
3)转换完成
三、中缀表达式转后缀表达式(代码实现)
算法思路
1.初始化两个栈:运算符栈operStack和存储结果的栈resStack 2.从左至右扫描中缀表达式 3.遇到操作数时(数字),直接将其压入栈resStack 4.遇到运算符时(+、-、*、/),比较其与operStack栈顶运算符的优先级 4.1 如果operStack为空,或operStack栈顶运算符为左括号"(",则直接将此运算符压入栈operStack; 4.2 否则,若优先级比operStack栈顶运算符优先级高,则将此运算符压入栈operStack; 4.3 否则,将operStack栈顶的运算符弹出并压入到栈resStack,再次转到4与operStack中新的栈顶运算符相比较 5.遇到括号时: 5.1 如果是左括号("("),则直接压入栈resStack 5.2 如果是左括号(")"),则依次弹出operStack栈顶的运算符,并压入resStack,直到遇到左括号为止,并且把左括号弹出栈operStack,此时这一对括号丢弃 6.重复步骤2到5,直到遍历完整个表达式 7.将operStack中剩余的运算符依次弹出并压入resStack 8.依次弹出resStack中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式
代码实现
public static ArrayList<String> InfixChangeToPostfix(ArrayList<String> tokens) { // step1:初始化两个栈:运算符栈numStack和存储结果的栈resStack Stack<String> operStack = new Stack<>(); Stack<String> resStack = new Stack<>(); // step2:从左至右扫描中缀表达式 for (String item : tokens) { if ("+".equals(item) || "-".equals(item) || "*".equals(item) || "/".equals(item)) { // 如果遇到运算符时 if (operStack.isEmpty() || "(".equals(operStack.peek())) { operStack.push(item); } else if (priority(item) > priority(operStack.peek())) { operStack.push(item); } else { // 当前操作符比栈顶操作符 优先级小或者相等 while (!operStack.isEmpty() && priority(operStack.peek()) >= priority(item)) { resStack.push(operStack.pop()); } // 还需将item压入operStack栈 operStack.push(item); } } else if ("(".equals(item) || ")".equals(item)) { // 遇到括号时 // 如果是左括号,则直接压入numStack if ("(".equals(item)) { operStack.push(item); } // 如果是右括号,则依次弹出numStack栈顶的运算符,并压入resStack,直到遇到左括号为止,此时将这一对括号丢弃 if (")".equals(item)) { while (!"(".equals(operStack.peek())) { resStack.push(operStack.pop()); } // 此时operStack栈顶元素为(,将其弹出 operStack.pop(); } } else { // 数字的话,直接压入resStack resStack.push(item); } } // step3:将numStack中剩余的运算符依次弹出并压入resStack while (!operStack.isEmpty()) { resStack.push(operStack.pop()); } // step4:依次弹出resStack的元素并输出,结果的逆序即为表达式对应的后缀表达式 ArrayList<String> list = new ArrayList<>(); while (!resStack.isEmpty()) { list.add(resStack.pop()); } Collections.reverse(list); //结果的逆序即为中缀表达式对应的后缀表达式 return list; }
public static ArrayList<String> InfixChangeToPostfix(ArrayList<String> tokens) { // step1:初始化两个栈:运算符栈numStack和存储结果的栈resStack Stack<String> operStack = new Stack<>(); Stack<String> resStack = new Stack<>(); // step2:从左至右扫描中缀表达式 for (String item : tokens) { if ("+".equals(item) || "-".equals(item) || "*".equals(item) || "/".equals(item)) { // 如果遇到运算符时 if (operStack.isEmpty() || "(".equals(operStack.peek())) { operStack.push(item); } else if (priority(item) > priority(operStack.peek())) { operStack.push(item); } else { // 当前操作符比栈顶操作符 优先级小或者相等 while (!operStack.isEmpty() && priority(operStack.peek()) >= priority(item)) { resStack.push(operStack.pop()); } // 还需将item压入operStack栈 operStack.push(item); } } else if ("(".equals(item) || ")".equals(item)) { // 遇到括号时 // 如果是左括号,则直接压入numStack if ("(".equals(item)) { operStack.push(item); } // 如果是右括号,则依次弹出numStack栈顶的运算符,并压入resStack,直到遇到左括号为止,此时将这一对括号丢弃 if (")".equals(item)) { while (!"(".equals(operStack.peek())) { resStack.push(operStack.pop()); } // 此时operStack栈顶元素为(,将其弹出 operStack.pop(); } } else { // 数字的话,直接压入resStack resStack.push(item); } } // step3:将numStack中剩余的运算符依次弹出并压入resStack while (!operStack.isEmpty()) { resStack.push(operStack.pop()); } // step4:依次弹出resStack的元素并输出,结果的逆序即为表达式对应的后缀表达式 ArrayList<String> list = new ArrayList<>(); while (!resStack.isEmpty()) { list.add(resStack.pop()); } Collections.reverse(list); //结果的逆序即为中缀表达式对应的后缀表达式 return list; }
public static ArrayList<String> InfixChangeToPostfix(ArrayList<String> tokens) { // step1:初始化两个栈:运算符栈numStack和存储结果的栈resStack Stack<String> operStack = new Stack<>(); Stack<String> resStack = new Stack<>(); // step2:从左至右扫描中缀表达式 for (String item : tokens) { if ("+".equals(item) || "-".equals(item) || "*".equals(item) || "/".equals(item)) { // 如果遇到运算符时 if (operStack.isEmpty() || "(".equals(operStack.peek())) { operStack.push(item); } else if (priority(item) > priority(operStack.peek())) { operStack.push(item); } else { // 当前操作符比栈顶操作符 优先级小或者相等 while (!operStack.isEmpty() && priority(operStack.peek()) >= priority(item)) { resStack.push(operStack.pop()); } // 还需将item压入operStack栈 operStack.push(item); } } else if ("(".equals(item) || ")".equals(item)) { // 遇到括号时 // 如果是左括号,则直接压入numStack if ("(".equals(item)) { operStack.push(item); } // 如果是右括号,则依次弹出numStack栈顶的运算符,并压入resStack,直到遇到左括号为止,此时将这一对括号丢弃 if (")".equals(item)) { while (!"(".equals(operStack.peek())) { resStack.push(operStack.pop()); } // 此时operStack栈顶元素为(,将其弹出 operStack.pop(); } } else { // 数字的话,直接压入resStack resStack.push(item); } } // step3:将numStack中剩余的运算符依次弹出并压入resStack while (!operStack.isEmpty()) { resStack.push(operStack.pop()); } // step4:依次弹出resStack的元素并输出,结果的逆序即为表达式对应的后缀表达式 ArrayList<String> list = new ArrayList<>(); while (!resStack.isEmpty()) { list.add(resStack.pop()); } Collections.reverse(list); //结果的逆序即为中缀表达式对应的后缀表达式 return list; }
测试
public static void main(String[] args) { ArrayList<String> infixList = new ArrayList<>(); // 中缀表达式 String infixExpression = "1+((2+3)*4)-5"; char[] chs = infixExpression.toCharArray(); for (char ch : chs) { infixList.add(ch + ""); // char转String的小技巧 } System.out.println("中缀表达式:" + infixList); ArrayList<String> postfixList = InfixChangeToPostfix(infixList); System.out.println("后缀表达式:" + postfixList); }
运行结果
中缀表达式:[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5] 后缀表达式:[1, 2, 3, +, 4, *, +, 5, -]
四、后缀表达式求值(逆波兰表达式求值)
即根据逆波兰表示法(后缀表达式),求表达式的值。
算法思路
从左至右扫描表达式 若遇到数字,则将数字压入堆栈 遇到运算符时,弹出栈顶的两个数(分别为栈顶元素和次顶元素),用元素对它们做相应的计算,并将结果入栈 重复上述过程直到表达式最右端 最后栈的最后一个元素即为表达式的结果
样例
代码实现
// 后缀表达式求值(逆波兰表达式求值) public static int evalRPN(ArrayList<String> list) { Stack<Integer> stack = new Stack<>(); for (String item : list) { if ("+".equals(item) || "-".equals(item) || "*".equals(item) || "/".equals(item)) { int num1 = stack.pop(); // 栈顶元素 int num2 = stack.pop(); // 次顶元素 switch (item) { case "+" : stack.push(num1 + num2);break; case "-" : stack.push(num2 - num1);break; case "*" : stack.push(num1 * num2);break; case "/" : stack.push(num2 / num1);break; } } else { stack.push(Integer.parseInt(item)); } } return stack.pop(); }
对应LeetCode一题:LeetCode150. 逆波兰表达式求值
五、中缀表达式转后缀表达式并计算结果(代码实现)
前提:操作数为整数
并且运算符为+ 、 - 、 * 、 /
代码实现
package 栈; import java.util.ArrayList; import java.util.Collections; import java.util.Stack; public class 中缀表达式转后缀表达式 { public static void main(String[] args) { ArrayList<String> infixList = new ArrayList<>(); // 中缀表达式 String infixExpression = "1+((2+3)*4)-5"; char[] chs = infixExpression.toCharArray(); for (char ch : chs) { infixList.add(ch + ""); // char转String的小技巧 } System.out.println("中缀表达式:" + infixList); ArrayList<String> postfixList = InfixChangeToPostfix(infixList); System.out.println("后缀表达式:" + postfixList); int res = evalRPN(postfixList); System.out.println("后缀表达式的值为:" + res); } public static ArrayList<String> InfixChangeToPostfix(ArrayList<String> tokens) { // step1:初始化两个栈:运算符栈numStack和存储结果的栈resStack Stack<String> operStack = new Stack<>(); Stack<String> resStack = new Stack<>(); // step2:从左至右扫描中缀表达式 for (String item : tokens) { if ("+".equals(item) || "-".equals(item) || "*".equals(item) || "/".equals(item)) { // 如果遇到运算符时 if (operStack.isEmpty() || "(".equals(operStack.peek())) { operStack.push(item); } else if (priority(item) > priority(operStack.peek())) { operStack.push(item); } else { // 当前操作符比栈顶操作符 优先级小或者相等 while (!operStack.isEmpty() && priority(operStack.peek()) >= priority(item)) { resStack.push(operStack.pop()); } // 还需将item压入operStack栈 operStack.push(item); } } else if ("(".equals(item) || ")".equals(item)) { // 遇到括号时 // 如果是左括号,则直接压入numStack if ("(".equals(item)) { operStack.push(item); } // 如果是右括号,则依次弹出numStack栈顶的运算符,并压入resStack,直到遇到左括号为止,此时将这一对括号丢弃 if (")".equals(item)) { while (!"(".equals(operStack.peek())) { resStack.push(operStack.pop()); } // 此时operStack栈顶元素为(,将其弹出 operStack.pop(); } } else { // 数字的话,直接压入resStack resStack.push(item); } } // step3:将numStack中剩余的运算符依次弹出并压入resStack while (!operStack.isEmpty()) { resStack.push(operStack.pop()); } // step4:依次弹出resStack的元素并输出,结果的逆序即为表达式对应的后缀表达式 ArrayList<String> list = new ArrayList<>(); while (!resStack.isEmpty()) { list.add(resStack.pop()); } Collections.reverse(list); //结果的逆序即为中缀表达式对应的后缀表达式 return list; } // 返回运算符的优先级,优先级是程序员来确定的,优先级使用数字表示 // 数字越大,则优先级就越高 // 假定目前只有 四种运算符: + - * / public static int priority(String oper) { if ("*".equals(oper) || "/".equals(oper)) { return 1; } else if ("+".equals(oper) || "-".equals(oper)) { return 0; } else { return -1; } } // 后缀表达式求值(逆波兰表达式求值) public static int evalRPN(ArrayList<String> list) { Stack<Integer> stack = new Stack<>(); for (String item : list) { if ("+".equals(item) || "-".equals(item) || "*".equals(item) || "/".equals(item)) { int num1 = stack.pop(); // 栈顶元素 int num2 = stack.pop(); // 次顶元素 switch (item) { case "+" : stack.push(num1 + num2);break; case "-" : stack.push(num2 - num1);break; case "*" : stack.push(num1 * num2);break; case "/" : stack.push(num2 / num1);break; } } else { stack.push(Integer.parseInt(item)); } } return stack.pop(); } }
运行结果
中缀表达式:[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5] 后缀表达式:[1, 2, 3, +, 4, *, +, 5, -] 后缀表达式的值为:16
这篇关于逆波兰算法、中缀表达式转后缀表达式的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-26JavaScript入门教程:从零开始学习JavaScript编程
- 2024-12-26JavaScript入门教程:从零开始学习JavaScript
- 2024-12-26JS编程入门指南:从零开始学习JavaScript
- 2024-12-25Java编程面试题详解与解答
- 2024-12-25TS基础知识详解:初学者必看教程
- 2024-12-252024面试题解析与攻略:从零开始的面试准备指南
- 2024-12-25数据结构与算法学习:新手入门教程
- 2024-12-25初学者必备:订单系统资料详解与实操教程
- 2024-12-24内网穿透资料入门教程
- 2024-12-24微服务资料入门指南