-
Notifications
You must be signed in to change notification settings - Fork 0
/
postfix using stack
62 lines (60 loc) · 1.93 KB
/
postfix using stack
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
import java.util.Stack;
public class postfix {
public static void main(String[] args) {
String str = "9-(5+3)*4/6";
Stack<String> val = new Stack<>();
Stack<Character> op = new Stack<>();
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (Character.isDigit(ch)) {
StringBuilder num = new StringBuilder();
num.append(ch);
while (i + 1 < str.length() && Character.isDigit(str.charAt(i + 1))) {
num.append(str.charAt(++i));
}
val.push(num.toString());
} else if (ch == '(') {
op.push(ch);
} else if (ch == ')') {
while (!op.isEmpty() && op.peek() != '(') {
String v2 = val.pop();
String v1 = val.pop();
char o = op.pop();
String t = v1 + v2+o;
val.push(t);
}
op.pop(); // Remove '('
} else {
while (!op.isEmpty() && precedence(ch) <= precedence(op.peek())) {
String v2 = val.pop();
String v1 = val.pop();
char o = op.pop();
String t = v1 + v2 + o;
val.push(t);
}
op.push(ch);
}
}
while (!op.isEmpty()) {
String v2 = val.pop();
String v1 = val.pop();
char o = op.pop();
String t = v1 + v2 + o;
val.push(t);
}
String pre = val.pop();
System.out.println(pre);
}
private static int precedence(char op) {
switch (op) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return 0;
}
}
}