Repository navigation
Expand file tree
/
Copy pathInfixPrefixPostfix.java
More file actions
89 lines (75 loc) · 1.79 KB
/
Copy pathInfixPrefixPostfix.java
File metadata and controls
89 lines (75 loc) · 1.79 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
package stackProblems1;
import java.util.ArrayDeque;
public class InfixPrefixPostfix {
static boolean isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
static int precedence(char c) {
if(c == '+' || c == '-') return 1;
else if(c == '*' || c == '/') return 2;
else return -1;
}
static int calculate(int a, int b, char c) {
switch(c) {
case '+':
return a+b;
case '-':
return a-b;
case '*':
return a*b;
case '/':
return a/b;
}
return 0;
}
static String infixToPostfix(String s) {
StringBuilder sb = new StringBuilder();
ArrayDeque<Character> stack = new ArrayDeque<>();
for(int i = 0; i<s.length(); i++) {
char cur = s.charAt(i);
if(cur == '(') {
stack.push(cur);
} else if(cur == ')') {
while(stack.peek() != '(') {
sb.append(stack.pop());
}
stack.pop();
} else if(isOperator(cur)) {
while(!stack.isEmpty() &&
precedence(cur) <= precedence(stack.peek())) {
sb.append(stack.pop());
}
stack.push(cur);
} else {
sb.append(cur);
}
}
while(!stack.isEmpty()) {
sb.append(stack.pop());
}
return sb.toString();
}
static int evaluatePostfix(String s) {
ArrayDeque<Integer> stack = new ArrayDeque<>();
for(int i = 0; i<s.length(); i++) {
char cur = s.charAt(i);
if(isOperator(cur)) {
int second = stack.pop();
int first = stack.pop();
int eval = calculate(first, second, cur);
stack.push(eval);
} else {
stack.push(cur-'0');
}
}
return stack.pop();
}
public static void main(String[] args) {
// String input = "(a+b/c)*((g/e)-f)";
String input = "(2*3)-(4/5-6+7)";
String output = infixToPostfix(input);
System.out.println(output);
int evaluate = evaluatePostfix(output);
System.out.println(evaluate);
}
}