blob: bd2cde9964ef109e23cd1ad4a0c4de1aba6b5267 (
plain)
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
|
/* Todo
* - Add support for trigonometric functions
* - Remove all edge cases
*/
import java.util.Stack;
import java.util.StringJoiner;
public class Parser {
private String expr;
private String postfix;
private Stack<Character> operatorStack;
public Parser(String infixExpr) {
expr = infixExpr.trim().replaceAll("\\s", ""); // remove whitespaces
postfix = toPostFix();
}
private boolean isOperand(char c) {
switch (c) {
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
return true;
default:
return false;
}
}
private boolean isOperand(String c) {
return isOperand(c.charAt(0));
}
private int getPresedence(char c) {
switch (c) {
case '^':
return 3;
case '/':
return 2;
case '*':
return 2;
case '+':
return 1;
case '-':
return 1;
default:
return -1;
}
}
private boolean hasLeftAssociativity(char c) {
if (c == '^') {
return false;
} else {
return true;
}
}
private String toPostFix() {
operatorStack = new Stack<>();
StringJoiner output = new StringJoiner(" ");
StringBuilder operand = new StringBuilder();
char[] infix = expr.replaceAll(" ", "").toCharArray();
// Main Expression Iteration
for (int i = 0; i < infix.length; i++) {
char c = infix[i];
// Keep appending digits to the operand StringBuilder and skip iterations till
// we find a operator.
if (isOperand(c)) {
operand.append(infix[i]);
if (i < infix.length - 1) {
continue;
}
}
if (operand.length() > 0) {
output.add(operand.toString());
operand = new StringBuilder();
}
if (c == '(') {
operatorStack.push(c);
} else if (c == ')') {
while (!operatorStack.isEmpty() && operatorStack.peek() != '(') {
output.add(operatorStack.pop().toString());
}
operatorStack.pop();
} else {
// Manage precedence order of operatorStack operators
while (!operatorStack.isEmpty() && getPresedence(c) <= getPresedence((char) operatorStack.peek())
&& hasLeftAssociativity(c)) {
output.add(operatorStack.pop().toString());
}
// For whatever reason, the last digit gets added to the operatorStack, leading
// to a duplicate of last digit in the expression
// To fix this, we again make sure that the current char is not a operand.
if (!isOperand(c)) {
operatorStack.push(c);
}
}
}
// pop all the operators left in the operatorStack after the loop is done.
while (!operatorStack.isEmpty()) {
if (operatorStack.peek() == '(') {
return "This expression is invalid";
}
output.add(operatorStack.pop().toString());
}
return output.toString();
}
private Double evaluate(String operator, Double op1, Double op2) {
switch (operator.charAt(0)) {
case '+':
return op2 + op1;
case '-':
return op1 - op2;
case '*':
return op2 * op1;
case '/':
return op1 / op2;
case '^':
return (Math.pow(op2, op1));
default:
return 0.0;
}
}
public double eval() {
Stack<Double> stack = new Stack<Double>();
for (String c : postfix.split(" ")) {
if (isOperand(c)) {
stack.push(Double.parseDouble(c));
} else {
Double op1 = (Double) (stack.pop());
Double op2 = (Double) (stack.pop());
stack.push(evaluate(c, op2, op1));
}
}
return stack.pop();
}
public String getPostfix() {
return postfix;
}
}
|
