Java代码实现中缀表达式转后缀表达式
2021/11/4 11:10:01
本文主要是介绍Java代码实现中缀表达式转后缀表达式,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
中缀转后缀
思路分析:
1)初始化两个栈:运算符栈s1和中间结果栈s2
2)从左到右扫描中缀表达式
3)遇到操作数将其压入s2
4)遇到操作符时,将其与s1栈顶运算符比较优先级
4.1)如果s1为空,或者栈顶元素为“(”直接将其压入运算符栈
4.2)如果优先级比s1栈顶元素的优先级高,将其直接入栈
4.3)如果优先级小于等于s1栈顶元素优先级,则将s1栈顶元素弹出并压入s2中,再次转到4.1与s1中新的栈顶元素比较
5)遇到括号
5.1)如果是左括号“(“,直接压入s1
5.2)如果是右括号”)“,则依次弹出s1栈顶元素,并压入s2,直到遇到”(“,并将这一对括号废弃
6)重复2~5步骤,直到表达式最右边
7)最后将其s1剩余运算符依次加入s2
8)依次弹出s2中元素输出结果就为后缀表达式
代码实现:
package com.cwnu.stack; import java.util.ArrayList; import java.util.List; import java.util.Stack; /* * 中缀转后缀的算法实现 * */ public class InfixtoSuffix { public static void main(String[] args) { //声明字符转 String express = "1 + ( ( 2 + 3 ) * 4 ) - 5"; //字符串转数组 String[] expressArray = toStringArray(express); //初始化两个栈符号栈s1和中间栈s2 Stack<String> s1 = new Stack<>(); Stack<String> s2 = new Stack<>(); s2 = suffixesToSuffixes(s1, s2, expressArray); String[] print = new String[s2.size()]; for (int i = 0; i < s2.size(); i++) { print[i] = s2.get(i); } System.out.print("表达式为:"); for (String e : print) { System.out.print(e + " "); } } //将字符串转化为数组 public static String[] toStringArray(String string) { return string.split(" "); } //运算优先级 public static int priority(String oper) { if (oper.equals("*") || oper.equals("/")) { return 1; } else if (oper.equals("+") || oper.equals("-")) { return 0; } else { return -1; } } //判断是否为运算符 public static boolean isOperator(String oper) { return oper.equals("*") || oper.equals("/") || oper.equals("+") || oper.equals("-"); } //判断是否为括号 public static boolean isParentheses(String oper) { return oper.equals("(") || oper.equals(")"); } //中缀转后缀 public static Stack suffixesToSuffixes(Stack<String> s1, Stack<String> s2, String[] strings) { //对表达时进行扫描 for (String itme : strings) { if (!isOperator(itme) && !isParentheses(itme)) {//表示为既不是运算符也不是括号,数字直接入s2 s2.push(itme); } else if (isOperator(itme)) {//遇到运算符 // 如果s1为空,或者栈顶元素为“(”直接将其压入运算符栈 if (s1.isEmpty() || s1.peek().equals("(")) { s1.push(itme); } else if (priority(itme) > priority(s1.peek())) {//如果优先级比s1栈顶元素的优先级高,将其直接入栈 s1.push(itme); } else if (priority(itme) <= priority(s1.peek())) {//如果优先级小于等于s1栈顶元素优先级,则将s1栈顶元素弹出并压入s2中,再次转到4.1与s1中新的栈顶元素比较 while (true) { s2.push(s1.pop()); if (s1.isEmpty() || s1.peek().equals("(") || priority(itme) > priority(s1.peek())) { s1.push(itme); break; } } } } else if (isParentheses(itme)) { // 5.1)如果是左括号“(“,直接压入s1 if (itme.equals("(")) { s1.push(itme); } //5.2)如果是右括号”)“,则依次弹出s1栈顶元素,并压入s2,直到遇到”(“,并将这一对括号废弃 if (itme.equals(")")) { while (true) { s2.push(s1.pop()); if (s1.peek().equals("(")) { s1.pop(); break; } } } } } while (true) { s2.push(s1.pop()); if (s1.isEmpty()) { break; } } return s2; } }
这篇关于Java代码实现中缀表达式转后缀表达式的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-22项目:远程温湿度检测系统
- 2024-12-21《鸿蒙HarmonyOS应用开发从入门到精通(第2版)》简介
- 2024-12-21后台管理系统开发教程:新手入门全指南
- 2024-12-21后台开发教程:新手入门及实战指南
- 2024-12-21后台综合解决方案教程:新手入门指南
- 2024-12-21接口模块封装教程:新手必备指南
- 2024-12-21请求动作封装教程:新手必看指南
- 2024-12-21RBAC的权限教程:从入门到实践
- 2024-12-21登录鉴权实战:新手入门教程
- 2024-12-21动态权限实战入门指南