蓝桥杯 表达式计算
题目
输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。
输入格式
输入一行，包含一个表达式。
输出格式
输出这个表达式的值。
输入样例
输出样例
数据规模和约定
表达式长度不超过100，表达式运算合法且运算过程都在int内进行。
思路
我居然手动实现了两个栈类！！！
- 预处理：如果前面是一个负号，需要在前面加一个0，使得表达式更加规范
- 遍历字符串
- 如果是数字则压栈(前面有数字则弹出合并再压栈)
- 如果是左括号，压栈
- 如果是右括号，弹出数据，计算后再压栈，再循环弹出，计算压栈直操作符栈为空或者为左括号。
- 如果是操作符，先压栈，然后判断符号优先级，如果优先级比较大，就先取出数据计算，然后压栈。
- 遍历完毕，计算剩下的表达式，直到操作符栈为空即为最后结果。
- 我做了float。理论上可以计算小数。
代码
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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
| import java.util.Scanner;
class CharStack {
private int maxSize;
private int top;
private char[] arr;
public CharStack(int size) {
maxSize = size;
top = -1;
arr = new char[maxSize];
}
public void push(char value) {
arr[++top] = value;
}
public char pop() {
char a = arr[top];
top--;
return a;
}
public char peek() {
if(isEmpty()){
return 0;
}
return arr[top];
}
public boolean isFull() {
return maxSize - 1 == top;
}
public boolean isEmpty() {
return top == -1;
}
}
class FloatStack {
private int maxSize;
private int top;
private float[] arr;
public FloatStack(int size) {
maxSize = size;
top = -1;
arr = new float[maxSize];
}
public void push(float value) {
arr[++top] = value;
}
public float pop() {
float a = arr[top];
top--;
return a;
}
public float peek() {
if(isEmpty()){
return 0;
}
return arr[top];
}
public boolean isFull() {
return maxSize - 1 == top;
}
public boolean isEmpty() {
return top == -1;
}
}
public class Main {
public static final int DEFAULT_STACK_SIZE = 100;
private static Boolean isInt(char c){
return (c>47&&c<58)?true:false;
}
private static Boolean isOperater(char c){
return (c=='+'||c=='-'||c=='*'||c=='/')?true:false;
}
private static Boolean isBigger(char c,char d){
int sc = (c=='*'||c=='/')?1:0;
int sd = (d=='*'||d=='/')?1:0;
if(c=='('||c==')'||d=='('||d==')'){
return false;
}else if(sc>=sd){
return true;
}else{
return false;
}
}
private static float doCalc(char o,float j,float k){
float result = 0;
if (o == '+') {
result = j+k;
}
if (o == '-') {
result = j-k;
}
if (o == '*') {
result = j*k;
}
if (o == '/') {
result = j/k;
}
return result;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String bdss = scanner.nextLine();
char[] bds = bdss.toCharArray();
if(bds[0] == '-'){
bds = "0".concat(bdss).toCharArray();
}
scanner.close();
CharStack operator = new CharStack(DEFAULT_STACK_SIZE);
FloatStack operand = new FloatStack(DEFAULT_STACK_SIZE);
for(int i = 0;i<bds.length;i++){
if(isInt(bds[i])){
if(i!=0&&isInt(bds[i-1])){
float a = operand.pop();
operand.push(a*10+(bds[i]-48));
}else {
operand.push((bds[i])-48);
}
continue;
}
if('(' == bds[i]){
operator.push(bds[i]);
continue;
}
if(')' == bds[i]){
while(!operator.isEmpty()&&operator.peek()!='('){
char op = operator.pop();
float j = operand.pop();
float k = operand.pop();
float result = doCalc(op, k, j);
if(result<0&&operator.peek()=='-'){
result = -result;
if(operator.peek()=='-'){
operator.pop();
operator.push('+');
}
}
operand.push(result);
}
if(operator.peek()=='('){
operator.pop();
}
continue;
}
if(isOperater(bds[i])){
if(bds[i] == '-' && bds[i-1] == '('){
operand.push(0);
}
while(isBigger(operator.peek(), bds[i])&&(!operator.isEmpty())){
char op = operator.pop();
float j = operand.pop();
float k = operand.pop();
float result = doCalc(op, k, j);
if(result<0&&operator.peek()=='-'){
result = -result;
if(operator.peek()=='-'){
operator.pop();
operator.push('+');
}
}
operand.push(result);
}
operator.push(bds[i]);
continue;
}
}
while(!operator.isEmpty()){
char op = operator.pop();
float j = operand.pop();
float k = operand.pop();
float result = doCalc(op, k, j);
if(result<0&&operator.peek()=='-'){
result = -result;
if(operator.peek()=='-'){
operator.pop();
operator.push('+');
}
}
operand.push(result);
}
System.out.println((int)operand.peek());
}
}
|
