This is a pratice for computing basic +-*/ and () operations by opg algorithm.
Input 2*(3+4) should return 14
Input 2-+ should return Integer.MIN_VALUE
It is relatively easy to get the operator matrix like below. For eash, I ignore of using regular grammar, first, follow set to get this matrix.
0 1 2 3 4 5 6
+ - * / ( ) #
0 + < < < < > < na
1 - < < < < > < na
2 * > > < < > < na
3 / > > < < > < na
4 ( > > > > > na na
5 ) < < < < = < na
6 # < < < < na < na
The matrix[i][j] means when operator j is going to enter stack, and the stack top operator is operator i, the relationship between i and j. One thing to notice is that operators relationship is not symmetric. For example, we have ‘+’ < ‘-‘ and ‘-‘ < ‘+’.
Then, we maintain 2 stacks: number stack and operator stack. Every time, we compare next operator and top operator in stack. If next operator is less than top operator, then we pop number and operator stack to calculate. The result send back to number stack. If next operator is greater than top operator, then push next operator to operator stack. If equal, then pop operator stack. If nothing applied, it means there is a mistake.
This operator matrix doesn’t has number i as an operator. So we should avoid invalid string like “3(2+1)” or “(1+2)3”.
check my code on github: link