Java实现：中缀表达式转后缀表达式
开篇
本篇文章为学习记录整理，旨在使用Java实现中缀表达式转后缀表达式的逻辑代码。
步骤
初始化栈:
初始化两个栈：运算符栈s1和储存中间结果的栈s2;
从左向右扫描中缀表达式;
遇到操作数时，将其压入s2;
遇到运算符时，比较其与s1栈顶运算符的优先级;
判断:
若s1为空，或栈顶运算符为左括号“（”，则直接将此运算符入栈；
否则，若优先级比栈顶运算符的高，也将运算符压入s1;
否则，将s1栈顶的运算符弹出并压入到s2中，再次转到第一步判断（判断a）与s1中新的栈顶运算符相比较;
遇到括号时:
如果是左括号“(”，则直接压入到s1;
如果是右括号")",则依次弹出s1栈顶的运算符，并压入s2,直到遇到左括号为止，此时将这一对括号丢弃;
重复以上步骤，直到表达式的最右边;
将s1中剩余的运算符依次弹出并压入到s2;
依次弹出s2中的元素并输出，结果的逆序即为中缀表达式所对应的后缀表达式;
代码实现
package com.zyc.stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class PolandNotation {
public static void main(String[] args) {
// (3+4)*5-6 => 3 4 + 5 * 6 -
// (30 - 6 ) / 3 * 8 = 64
// String suffixExpression = "30 6 - 3 / 8 *";
//
// // 1. 先将表达式放入到ArrayList中
// // 2.将ArrayList传递给一个方法，遍历ArrayList配合栈完成计算
// List<String> list = getListString(suffixExpression);
// System.out.println("list="+list);
// int res = calculate(list);
// System.out.println("运算结构是: " + res);
// 实现中缀表达式转为后缀表达式的功能
/**
* 说明:
* 1. 1+((2+3)*4)-5 => 1 2 3 + 4 * + 5 -
* 2. 因为直接对str操作很不方便，因此先将"1+((2+3)*4)-5" 转成中缀表达式对应的List
* 即："1+((2+3)*4)-5" => ArrayList[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
* 3.将得到的中缀表达式对应的List转换成后缀表达式对应的List
* 即：ArrayList[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5] => ArrayList[1, 2, 3, +, 4, *, +, 5, -]
*/
String expression = "1+((2+3)*4)-5";
List<String> infixExpressionList = toInfixExpressionList(expression);
System.out.println(infixExpressionList);
List<String> suffixExpression = parseSuffixExpressionList(infixExpressionList);
System.out.println("后缀表达式对应的list:" + suffixExpression);
System.out.printf("expression=%d", calculate(suffixExpression));
}
// 3.将得到的中缀表达式对应的List转换成后缀表达式对应的List
//即：ArrayList[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5] => ArrayList[1, 2, 3, +, 4, *, +, 5, -]
public static List<String> parseSuffixExpressionList(List<String> ls) {
// 定义两个栈
Stack<String> s1 = new Stack<String>();// 符号栈
// 说明: 因为s2这个栈,在整个转换过程中，没有pop的操作, 而且后面我们还需要逆序输出
// 因此比较麻烦，所以这里我们不使用Stack,而是用List<String>来代替。
List<String> s2 = new ArrayList<String>(); // 储存中间结果的栈s2
// 遍历ls
for (String item : ls) {
// 如果是一个数，加入到s2
if (item.matches("\\d+")) {
s2.add(item);
} else if (item.equals("(")) {
s1.push(item);
} else if (item.equals(")")) {
// 如果是右括号")", 则依次弹出s1栈顶的运算符，并压入到s2,直到遇到左括号为止，此时将这一对括号丢弃
while (!s1.peek().equals("(")) {
s2.add(s1.pop());
}
s1.pop(); // 将"("弹出s1栈，消除小括号
} else {
// 当item的优先级小于等于s1栈顶运算符，将s1栈顶的运算符弹出并加入到s2中，然后再次进行比较
while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
s2.add(s1.pop());
}
// 将item压入栈
s1.push(item);
}
}
// 将s1中剩余的运算符依次弹出并加入到s2中
while (s1.size() != 0) {
s2.add(s1.pop());
}
return s2;
}
// 方法: 将中缀表达式转换成对应的list
public static List<String> toInfixExpressionList(String s) {
// 定义一个list,存放中缀表达式对应的内容
List<String> ls = new ArrayList<String>();
int i = 0; // 这是一个指针，用于遍历中缀表达式字符串
String str; // 对多位数的拼接
char c; // 每遍历一个字符，就放入到c
do {
// 如果c是一个非数字，需要加入到ls
if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) >57) {
ls.add("" + c);
i++;// 指针后移
} else {// 如果是一个数，需要考虑多位数
str = ""; // 先将str置成"", '0'[48] -> '9'[57]
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;
}
/**
* 完成对逆波兰表达式的计算
* 从左至右扫描，将3和4压入堆栈;
* 遇到+运算符，因此弹出4和3（4是栈顶元素，3是次顶元素），计算出3+4的值，得7，再将7入栈;
* 将5入栈;
* 接下来是*运算符，因此弹出5和7，计算出5*7=35, 将35入栈
* 将6入栈
* 最后是-运算符，计算出35-6的值，即29，因此得出最终结果
* @param list
* @return
*/
public static int calculate(List<String> list) {
// 创建栈
Stack<String> stack = new Stack<>();
// 遍历
for (String item :list) {
// 这里使用正则来取出数
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("运算符错误");
}
// res入栈
stack.push("" + res);
}
}
// 最后留在栈中的就是运算结果
return Integer.parseInt(stack.pop());
}
// 将一个逆波兰表达式，依次将数据和运算符放入到ArrayList中
public static List<String> getListString(String suffixExpression) {
// 将suffixExpression分割
String[] split = suffixExpression.split(" ");
List<String> list = new ArrayList<>();
for(String ele: split) {
list.add(ele);
}
return list;
}
}
// 编写一个类Operation, 可以返回一个运算符对应的优先级
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;
}
}
注
以上便是本文的全部内容，希望也能对您起到参考作用。
感谢阅读！
原文地址：https://blog.csdn.net/qq_26854355/article/details/142420661
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！