<>中缀表达式转后缀表达式

中缀表达式转后缀表达式的思路步骤分析。

* 初始化一个栈和一个队列,运算符栈 S1 和存储中间结果的队列 Q1
* 从左至右扫描中缀表达式
* 遇到操作数时放入队列 Q1 中
* 遇到运算符时,比较其与S1栈顶运算符的优先级
* 如果S1为空,或栈顶运算符为左括号 ( ,则直接将此运算符入栈
* 否则,若优先级比栈顶运算符的高,也将运算符压入S1
* 否则,将S1 栈顶的运算符弹出并添加到Q1 中,再次转到(4.1) 与S1 中新的栈顶运算符相比较
* 遇到括号时
* 如果是左括号( ,则直接压入S1
* 如果是右括号 ) ,则依次弹出S1 栈顶的运算符,并添加到Q1,直到遇到左括号为止,此时将这一对括号丢弃
* 重复步骤2至5,直到表达式的最右边
* 将S1 中剩余的运算符依次弹出并添加到Q1
* 依次取出 Q1 中的元素并输出,结果就是中缀表达式对应的后缀表达式。
<>实现代码
package com.codestd.study.stack; import org.apache.commons.lang3.StringUtils;
import java.util.ArrayDeque; import java.util.Queue; import java.util.Stack;
/** * 后缀表达式 * * @author jaune * @since 1.0.0 */ public class SuffixExpression {
/** * 中缀表达式转后缀表达式 * * @param expression 表达式 */ public String toSuffix(String
expression) { String[] expItems = StringUtils.split(expression, ' '); Stack<
String> operator = new Stack<>(); Queue<String> exp = new ArrayDeque<>(); for (
int i = 0; i < expItems.length; i++) { String expItem = expItems[i]; if (this.
isNumber(expItem)) { exp.add(expItem); } else if (this.isOperator(expItem)) {
this.operatorHandle(operator, exp, expItem); } else if (this.isBracket(expItem))
{ if (this.isOpeningBracket(expItem)) { operator.push(expItem); } else { while (
!operator.peek().equals("(")) { exp.add(operator.pop()); } operator.pop(); } } }
while (!operator.isEmpty()) { exp.add(operator.pop()); } return StringUtils.join
(exp, " "); } private void operatorHandle(Stack<String> operator, Queue<String>
exp, String s) { if (operator.isEmpty() || this.isOpeningBracket(operator.peek()
)) { operator.push(s); } else if (this.getPriority(s) > this.getPriority(
operator.peek())) { operator.add(s); } else { exp.add(operator.pop()); this.
operatorHandle(operator, exp, s); } } private boolean isNumber(String s) {
return s.matches("\\d+"); } private boolean isOperator(String s) { return "+".
equals(s) || "-".equals(s) || "*".equals(s) || "/".equals(s); } private boolean
isBracket(String s) { return "(".equals(s) || ")".equals(s); } private boolean
isOpeningBracket(String s) { return "(".equals(s); } private int getPriority(
String s) { if ("+".equals(s) || "-".equals(s)) { return 1; } else if ("*".
equals(s) || "/".equals(s)) { return 2; } else { throw new RuntimeException(
"不识别此符号"); } } }
<>后缀表达式计算

后缀表达式是非常适合计算机计算的表达式。1 + ( ( 2 + 3 ) * 4 ) - 5对应的后缀表达式是1 2 3 + 4 * + 5 -。
计算法方式很简单,创建一个栈S1,从左到右依次扫描表达式,遇到数值则放入栈中;遇到运算符,则从栈S1中弹出两个数值,并计算表达式的值,然后重新入栈。

后缀表达式的计算比较简单,这里就不实现代码了。有兴趣的同学可以自己实现以下。

技术
©2019-2020 Toolsou All rights reserved,
JQ get请求 拼接 url 参数 (查询条件)使用VS2019 “Windows桌面应用程序”模块创建Win32窗口Java Thread之Sleep()使用方法总结习题11-5 指定位置输出字符串jmeter-while控制器使用总结指定位置输出字符串(详细解析)[work] python读取txt文件最后一行mybatis系列之返回结果映射 mysql无备份恢复【Python】读取txt文件,获取指定行中指定位置数据