-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathPostfixExpression.java
More file actions
91 lines (76 loc) · 2.04 KB
/
PostfixExpression.java
File metadata and controls
91 lines (76 loc) · 2.04 KB
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
package com.duke.stack;
import java.util.Stack;
public class PostfixExpression {
public static void main(String[] args) {
// String str = "3+2*2";
String str = "2+3*4-5+7/2";
String postfixExpr = postfix(str);
System.out.println("Postfix Expression: " + postfixExpr);
solvePostExpression(postfixExpr);
}
private static void solvePostExpression(String expressStr) {
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < expressStr.length(); i++) {
char ch = expressStr.charAt(i);
if (Character.isDigit(ch)) {
stack.push(Character.getNumericValue(ch));
} else {
int b = stack.pop();
int a = stack.pop();
stack.push(calculate(a, b, ch));
}
}
System.out.println("Output: " + stack.pop());
}
private static String postfix(String exp) {
StringBuilder expression = new StringBuilder();
Stack<Character> st = new Stack<>();
for (int i = 0; i < exp.length(); i++) {
char ch = exp.charAt(i);
if (Character.isDigit(ch)) {
expression.append(ch);
} else {
if (!st.isEmpty()) {
char peek = st.peek();
if (getPrecedence(ch) > getPrecedence(peek)) {
st.push(ch);
} else if (getPrecedence(ch) <= getPrecedence(peek)) {
while (!st.isEmpty()) {
char popped = st.pop();
expression.append(popped);
}
st.push(ch);
}
} else {
st.push(ch);
}
}
}
while (!st.isEmpty()) {
char popped = st.pop();
expression.append(popped);
}
return expression.toString();
}
private static int getPrecedence(char operator) {
if (operator == '+' || operator == '-') {
return 1;
} else if (operator == '*' || operator == '/') {
return 2;
}
return 0;
}
private static int calculate(int a, int b, char operator) {
int res = 0;
if (operator == '*') {
res = a * b;
} else if (operator == '-') {
res = a - b;
} else if (operator == '/') {
res = a / b;
} else if (operator == '+') {
res = a + b;
}
return res;
}
}