java栈实现中缀转后缀并计算后缀表达式
程序员文章站
2022-03-10 19:55:32
...
https://www.bilibili.com/video/av54029771?p=42
public class PolandNotation {
public static void main(String[] args) {
// 完成将一个中缀表达式转成后缀表达式的功能
// 1. 1+((2+3)*4)-5 => 1 2 3 + 4 * + 5 -
// 2. 因直接对str进行操作,不方便,所以将中缀表达式转为list进行操作,
// 即 1+((2+3)*4)-5 => [1,+,(,(,2,+,3,),*,4,),-,5]
String expression = "1+((2+3)*4)-5";
List<String> inFixList = toInFixExpressionString(expression);
System.out.println(inFixList);
// 3.将中缀表达式list转为后缀表达式的list
// [1,+,(,(,2,+,3,),*,4,),-,5] ==》 [1,2,3,+,4,*,+,5,-]
List<String> suffixList = parseSuffixExpressionList(inFixList);
System.out.println(suffixList);
}
//将表达式字符串(没有空格)转为list返回,支持()
public static List<String> toInFixExpressionString(String s){
List<String> list = new ArrayList<String>();
int i = 0;//遍历字符串的索引
StringBuilder str =new StringBuilder();//用于多位数拼接
char c;//接受每一个扫描的字符
while (i<s.length()){
//如果是非数字,则直接加入list
if((c=s.charAt(i))<48||(c=s.charAt(i))>57){
list.add(c+"");
i++;
}else{
//如果是数字,进行多位数拼接
while (i<s.length()&&(c=s.charAt(i))>=48&&(c=s.charAt(i))<=57){
str.append(c);
i++;
}
list.add(str.toString());
str.delete(0,str.length());
}
}
return list;
}
// 中缀表达式转后缀表达式
public static List<String> parseSuffixExpressionList(List<String> ls){
//定义两个栈
Stack<String> s1 = new Stack<>(); // 符号栈
List<String> s2 = new ArrayList<>();//存放结果的集合,没有pop操作所以不用栈
for (String item : ls) {
if(item.matches("\\d+")){//遇到操作数
s2.add(item);
} else if (item.equals("(")) {//遇到(
s1.add(item);
} else if (item.equals(")")) {//遇到)
while(!s1.peek().equals("(")){
s2.add(s1.pop());
}
s1.pop();//弹出(
}else{ // 遇到运算符
while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
s2.add(s1.pop());
}
s1.push(item);
}
}
while (s1.size() != 0) {
s2.add(s1.pop());
}
return s2;
}
}
// 返回运算符优先级的类
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;
}
}
// 对逆波兰表达式进行计算
public static int calculate(List<String> list){
// 只需要一个栈即可。
Stack<String> stack = new Stack<>();
for (String s : list) {
// 从左到右扫描
if(s.matches("\\d+")){//使用正则表达式进行判断,用于判断多位数
stack.push(s);
}else{
int num2 = Integer.parseInt(stack.pop());
int num1 = Integer.parseInt(stack.pop());
int res = 0;
if(s.equals("+")){
res=num1+num2;
} else if (s.equals("-")) {
res = num1-num2;
} else if (s.equals("*")) {
res = num1*num2;
} else if (s.equals("/")) {
res = num1/num2;
}
stack.push(res+"");
}
}
return Integer.parseInt(stack.pop());
}
}
public static void main(String[] args) {
// 完成将一个中缀表达式转成后缀表达式的功能
// 1. 1+((2+3)*4)-5 => 1 2 3 + 4 * + 5 -
// 2. 因直接对str进行操作,不方便,所以将中缀表达式转为list进行操作,
// 即 1+((2+3)*4)-5 => [1,+,(,(,2,+,3,),*,4,),-,5]
String expression = "1+((2+3)*4)-5";
List<String> inFixList = toInFixExpressionString(expression);
System.out.println(inFixList);
// 3.将中缀表达式list转为后缀表达式的list
// [1,+,(,(,2,+,3,),*,4,),-,5] ==》 [1,2,3,+,4,*,+,5,-]
List<String> suffixList = parseSuffixExpressionList(inFixList);
System.out.println(suffixList);
int calculate = calculate(suffixList);
System.out.println(suffixList+"计算结果为"+calculate);//16
}
上一篇: 数据结构第二章C语言———线性表
下一篇: 第五章 数组