This repository has been archived by the owner on Oct 29, 2020. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 179
/
shuntingYard.java
59 lines (52 loc) · 1.88 KB
/
shuntingYard.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
import java.util.Stack;
public class ShuntingYard {
public static void main(String[] args) {
String infix = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3";
System.out.printf("infix: %s%n", infix);
System.out.printf("postfix: %s%n", infixToPostfix(infix));
}
static String infixToPostfix(String infix) {
/* To find out the precedence, we take the index of the
token in the ops string and divide by 2 (rounding down).
This will give us: 0, 0, 1, 1, 2 */
final String ops = "-+/*^";
StringBuilder sb = new StringBuilder();
Stack<Integer> s = new Stack<>();
for (String token : infix.split("\\s")) {
if (token.isEmpty())
continue;
char c = token.charAt(0);
int idx = ops.indexOf(c);
// check for operator
if (idx != -1) {
if (s.isEmpty())
s.push(idx);
else {
while (!s.isEmpty()) {
int prec2 = s.peek() / 2;
int prec1 = idx / 2;
if (prec2 > prec1 || (prec2 == prec1 && c != '^'))
sb.append(ops.charAt(s.pop())).append(' ');
else break;
}
s.push(idx);
}
}
else if (c == '(') {
s.push(-2); // -2 stands for '('
}
else if (c == ')') {
// until '(' on stack, pop operators.
while (s.peek() != -2)
sb.append(ops.charAt(s.pop())).append(' ');
s.pop();
}
else {
sb.append(token).append(' ');
}
}
while (!s.isEmpty())
sb.append(ops.charAt(s.pop())).append(' ');
return sb.toString();
}
}