算法设计 计算表达式的值 java

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 day_19;
import java.util.Scanner;
import java.util.Stack;
/**
* 输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除
* 目前暂不支持负数
* 留下注释，明天再写
* Created by IamZY on 2018/1/17.
*
* @version 1.1
*/
public class Main {
public static void main(String[] args) {
String str = "1-2+3*(4-5)";
//数字栈
Stack<Integer> number = new Stack<Integer>();
//符号栈
Stack<Character> op = new Stack<Character>();
System.out.println(expressionToResult(str, number, op));
}
public static int expressionToResult(String str, Stack<Integer> number, Stack<Character> op) {
//将str转换为char[]
char[] chars = str.toCharArray();
//遍历char数组
for (char x : chars) {
if (x == '+' || x == '-' || x == '*' || x == '/') {
int opLevel = 0;
int thisOpLevel = optionLevel(x);
//取此时符号栈顶元素的优先值和此时的入栈的符号比较
if (!op.isEmpty()) {
//栈顶符号优先级
opLevel = optionLevel(op.peek());
//若此时将入栈的符号优先级小于栈顶符号优先级 则计算
if (thisOpLevel <= opLevel) {
int n1 = number.pop();
int n2 = number.pop();
int result = calResult(op.pop(), n2, n1);
number.push(result);
op.push(x);
} else {
// 如果此时将入栈的符号优先级大于栈顶符号优先级
op.push(x);
}
} else {
//符号栈为空 不比较直接加入符号栈
op.push(x);
}
} else if (x == '(') {
op.push(x);
} else if (x == ')') {
//出现右括号 找符号栈中的左括号
while (true) {
char opStack = op.pop();
if (opStack == '(') {
break;
} else {
//不是左括号就把()之间的数据运算
int n1 = number.pop();
int n2 = number.pop();
//将结果放回数据栈
number.push(calResult(opStack, n2, n1));
}
}
} else if (Character.isDigit(x)) {
//数字进栈
number.push(Integer.parseInt(String.valueOf(x)));
}
} //增强for...
// 遍历完表达式 栈中可能还有符号
while (true) {
if (op.isEmpty()) {
break;
} else {
int n1 = number.pop();
int n2 = number.pop();
number.push(calResult(op.pop(), n2, n1));
}
}
return number.pop();
}
//计算两个数的值
public static int calResult(char c, int x, int y) {
switch (c) {
case '+':
return x + y;
case '-':
return x - y;
case '*':
return x * y;
case '/':
return x / y;
default:
return -1;
}
}
//判断符号优先级的方法
public static int optionLevel(char c) {
switch (c) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return 0;
}
}
}