栈实现综合计算器
|字数总计:2.9k|阅读时长:11分钟|阅读量:|
栈的介绍
- 栈的英文为(stack)
- 栈是一个先入后出(FILO-First In Last Out)的有序列表。
- 栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
- 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。
- 栈的插入操作(push)，称压栈、入栈。类似子弹入弹夹。
栈的删除操作(pop)，叫作出栈，也有的叫作弹栈。如同弹夹中的子弹出夹。
栈的顺序存储结构
栈的链式存储结构
栈的应用场景
- 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出， 回到原来的程序中。
- 处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
- 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
- 二叉树的遍历。
- 图形的深度优先(depth一first)搜索法。
用数组模拟栈
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
| package com.nanzx.stack;
import java.util.Scanner;
public class ArrayStackDemo {
public static void main(String[] args) {
ArrayStack stack = new ArrayStack(4);
String key = "";
boolean loop = true;
Scanner scanner = new Scanner(System.in);
while (loop) {
System.out.println("show: 表示显示栈");
System.out.println("exit: 退出程序");
System.out.println("push: 表示添加数据到栈(入栈)");
System.out.println("pop: 表示从栈取出数据(出栈)");
System.out.println("请输入你的选择");
key = scanner.next();
switch (key) {
case "show":
stack.list();
break;
case "push":
System.out.println("请输入一个数");
int value = scanner.nextInt();
stack.push(value);
break;
case "pop":
try {
int res = stack.pop();
System.out.printf("出栈的数据是 %d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case "exit":
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出~~~");
}
}
class ArrayStack {
private int maxSize;
private int[] stack;
private int top = -1;
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
}
public boolean isFull() {
return top == maxSize - 1;
}
public boolean isEmpty() {
return top == -1;
}
public void push(int value) {
if (isFull()) {
System.out.println("栈满");
return;
}
top++;
stack[top] = value;
}
public int pop() {
if (isEmpty()) {
throw new RuntimeException("栈空，没有数据~");
}
int value = stack[top];
top--;
return value;
}
public void list() {
if (isEmpty()) {
System.out.println("栈空，没有数据~~");
return;
}
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}
}
|
前缀表达式（波兰式）
介绍
前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前。
举例说明： (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6
前缀表达式的计算机求值
从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 和 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。
例如: (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 , 针对前缀表达式求值步骤如下:
- 从右至左扫描，将6、5、4、3压入堆栈
- 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素），计算出3+4的值，得7，再将7入栈
- 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈
- 最后是-运算符，计算出35-6（栈顶元素 - 次顶元素）的值，即29，由此得出最终结果
中缀表达式
介绍
中缀表达式就是常见的运算表达式，如(3+4)×5-6
中缀表达式的计算机求值
使用栈完成中缀表达式的计算思路:
需要创建两个栈：数栈存放数字，符号栈存放运算符
通过一个 index 值（索引），来遍历我们的表达式
如果我们发现是一个数字, 就直接入数栈
如果发现扫描到是一个运算符, 就分如下情况:
如果当前的符号栈为空，就直接入栈。
如果符号栈有运算符，就进行比较：①当前运算符的优先级 <=** 栈中的操作符， 就需要从数栈中pop出两个数,再从符号栈中pop出一个运算符，进行运算，将得到结果压入数栈，然后将当前运算符压入符号栈。②当前运算符的优先级 **> 栈中的操作符， 就直接入符号栈。
当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运行
最后在数栈只有一个数字，就是表达式的结果
后缀表达式（逆波兰表达式）
介绍
后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后
举例说明： (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –
后缀表达式的计算机求值
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。
例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:
- 从左至右扫描，将3和4压入堆栈；
- 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
- 将5入栈；
- 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
- 将6入栈；
- 最后是-运算符，计算出35-6的值（次顶元素 - 栈顶元素），即29，由此得出最终结果
逆波兰计算器的实现
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
| package com.nanzx.stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class PolandNotation {
public static void main(String[] args) {
String suffixExpression = "9 3 1 - 3 * + 10 2 / +";
List<String> list = getListString(suffixExpression);
System.out.println(calculate(list));
}
public static List<String> getListString(String suffixExpression) {
String[] split = suffixExpression.split(" ");
List<String> list = new ArrayList<String>();
for (String ele : split) {
list.add(ele);
}
return list;
}
public static int calculate(List<String> list) {
Stack<String> stack = new Stack<String>();
for (String item : list) {
if (item.matches("\\d+")) {
stack.push(item);
} else {
int num1 = Integer.valueOf(stack.pop());
int num2 = Integer.valueOf(stack.pop());
int result = 0;
if (item.equals("+")) {
result = num1 + num2;
} else if (item.equals("*")) {
result = num1 * num2;
} else if (item.equals("-")) {
result = num2 - num1;
} else if (item.equals("/")) {
result = num2 / num1;
} else {
System.out.println("程序有异常！！！");
}
stack.push(result + "");
}
}
return Integer.valueOf(stack.pop());
}
}
|
将中缀表达式转换为后缀表达式
中缀表达式“9+(3-1)×3+10÷2”转化为后缀表达式“9 3 1 - 3 * + 10 2 / +”。
规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。
思路：
初始化：运算符栈stack和动态数组(ArrayList) list；
从左至右扫描中缀表达式；
遇到操作数时，将其添加到list中；
遇到运算符时，比较其与stack栈顶运算符的优先级：
- 如果stack为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
- 如果优先级比栈顶运算符的高，也将运算符压入stack；
- 如果优先级比栈顶运算符的低，将stack栈中的所有运算符弹出并追加到list中。
- 遇到括号时：
- 从左至右扫描中缀表达式结束后，将stack中剩余的运算符依次追加到list中。
代码实现：
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
| package com.nanzx.stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class PolandNotation {
public static void main(String[] args) {
String infixExpression = "9+(3-1)*3+10/2";
List<String> ls = toInfixExpressionList(infixExpression);
List<String> list = parseSuffixExpreesionList(ls);
System.out.println(ls);
System.out.println(list);
System.out.println(calculate(list));
}
public static int priority(String s) {
if (s.equals("*") || s.equals("/")) {
return 1;
} else if (s.equals("+") || s.equals("-")) {
return 0;
} else {
return -1;
}
}
public static List<String> toInfixExpressionList(String s) {
List<String> ls = new ArrayList<String>();
int i = 0;
String str;
char c;
do {
if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
ls.add("" + c);
i++;
} else {
str = "";
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;
}
public static List<String> parseSuffixExpreesionList(List<String> ls) {
Stack<String> stack = new Stack<String>();
List<String> list = new ArrayList<String>();
for (String ele : ls) {
if (ele.matches("\\d+")) {
list.add(ele);
} else if (ele.equals("(")) {
stack.push(ele);
} else if (ele.equals(")")) {
while (!stack.peek().equals("(")) {
list.add(stack.pop());
}
stack.pop();
} else {
while (stack.size() != 0 && priority(ele) <= priority(stack.peek())) {
list.add(stack.pop());
}
stack.push(ele);
}
}
while (stack.size() != 0) {
list.add(stack.pop());
}
return list;
}
}
|
微信
支付宝