中缀表达式转换为后缀表达式以及逆波兰计算器

algorithm

在写代码时,早早遇到过栈:

  1. 子程序调用:
    1. 在跳往子程序前,先将下个指令的地址存到堆栈中,直到子程序执行完毕再将地址取出,以回到原来的程序中。
    2. 换句话理解:一个函数中调用另一个函数时,会将这个函数现场保留(压栈),以便于被调用的函数执行完毕后,原函数直接出栈。
  2. 处理递归调用:
    1. 和子程序递归的调用类似,除了存储下一个指令的地址外,也将参数、区域变量等数据存入栈中。
  3. 表达式转换:如使用中缀表达式转换为后缀表达式,以便于求值;
  4. 二叉树的遍历;
  5. 图的深度优先遍历搜索;

基于栈的简单计算器

  • 中缀表达式–>中缀表达式 ArrayList:依次扫描字符,是字符直接入链表,否则拼接整个整数出来

    • 在ASCII表中 0-9的ASCII码为48-57
    • Java字符串遍历中s.charAt(i)可以快速指定位置的字符
  • 中缀表达式List –>后缀表达式:

    • 创建操作符栈s1,和临时结果栈s2(此处使用List,方便后续计算)
    • 依次扫描表达式,数字则入s2,
    • 考虑( )
    • 在s1非空时,将s1中优先级高的出栈,压栈到s1。可能会遗忘非空条件,因为这步操作目的是将此前优先级高的操作符取出。
  • 后缀表达式(逆波兰表达式)计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class PolandNotation {
public static void main(String[] args) {
//后缀表达式
String suffixExpression = "4 5 * 8 - 60 + 8 2 / +";

List<String> list = getListString(suffixExpression);
System.out.println("rpnList= " + list);
int res = calculate(list);
System.out.println("the Result = " + res);

System.out.println("========请输入中缀表达式,俺们自动计算=========");
Scanner sc = new Scanner(System.in);
String expression = sc.next();
List<String> expList = toExpressionList(expression);
List<String> suffixExpList = parseSuffixExpressionList(expList); //此处转换为后缀表达式
int res2 = calculate(suffixExpList);
System.out.println("Great, your expression Result = " + res2);
}


//中缀表达式list --》 后缀表达式list
public static List<String> parseSuffixExpressionList(List<String> ls){
//1. 定义栈
Stack<String> s1 = new Stack<>(); //符号栈
//注意 s2栈 在处理过程中 不需要pop 而是在完成后 用于后缀表达式计算
//所以不用Stack
List<String> s2 = new ArrayList<>(); //存储中间结果

//遍历ls
for (String item : ls){
if (item.matches("\\d+")){ //如果是一个数 直接加入s2
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中的运算符依次压入s2
}
s1.pop(); //弹出小括号
}else {
//上面解决了 数字直接压入s2 、
//当item 优先级小于等于 s1 栈顶的运算符 时,s1.pop()并加入s2中,item继续与s1.peek()比较
//换句话说,运算符 优先级高的优先入s2(中间结果)
while (s1.size() != 0 && Operation.getVlaue(s1.peek()) >= Operation.getVlaue(item)){
//运算符栈 中 >= 表达式中的这个时 将s1中的操作符 存入s2中
s2.add(s1.pop());
}
s1.push(item); //否则或结束后,将 本次遍历的item存入s1
}
}// end forloop ls
//遍历完毕表达式后,将s1中剩余的运算符弹出并加入s2
while (s1.size() != 0){
s2.add(s1.pop());
}
return s2; //因为我们存放的是List数据结构 ,直接按照顺序输出即可
}

//表达式(字符串) 转 List
/*
利用s1存储运算符,s2临时存储数。 注意优先级高的先压入栈s2
*/
public static List<String> toExpressionList(String s){
//list存放中缀表达式内容
List<String> ls = new ArrayList<>();
int i = 0; //遍历中缀表达式字符串 指针
String str; //用于对多位数拼接
char c; //遍历到字符
do{
if ((c=s.charAt(i)) < 48 || (c=s.charAt(i)) > 57){
//若c不是数字
ls.add("" + c);
i++;
}else { //若 c为数字
str = ""; //在ASCII中 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;
}

//将字符串表达式中 数字、运算符 放入ArrayList中
public static List<String> getListString(String suffixExpression){
//分割字符串
String[] split = suffixExpression.split(" ");
List<String> list = new ArrayList<>();
for (String ele : split){
list.add(ele);
}
return list;
}

//对逆波兰表达式(后缀表达式)运算
public static int calculate(List<String> ls){
//申请一个栈
Stack<String> stack = new Stack<String>();
for (String item : ls){
//使用正则表达式取出数
if (item.matches("\\d+")){ //匹配 数 则入栈
stack.push(item);
}else{ //否则为操作符 需要pop出两个数
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 {
//System.out.println("Sorry, we DONOT support the operator now!");
throw new RuntimeException("Sorry, we DONOT support the operator now!");
}
stack.push("" + res); //将计算解决压栈
}// end num cal
}//end for loop of ls
return Integer.parseInt(stack.pop()); //最后栈中的值为结果。
}
}

本文作者:Anthony

本文链接: https://www.youdef.com/posts/52.html

评论