I am coding a calculator class to learn Java. As of now, it can handle simple functions such as 2+2, 2^2, etc., but I am trying to implement Shunting Yard Algorithms so it can handle more complex expressions.
I am new to data structures and cannot code something like this without a guide, so after research I found several examples online and am following one of them found here. Other sites, if you are interested: 1, 2. I chose the first linked site because I understand it the best of the three.
But I don't understand what the author is doing here:
/** in stack precedence **/
private static final int[] isp = {0, 19, 12, 12, 13, 13, 13, 0};
/** incoming character precedence **/
private static final int[] icp = {20, 19, 12, 12, 13, 13, 13, 0};
I understand that this has something to do with the precedence of the operators, but I'm not sure where the numbers come from. Can someone please clarify?
Also, my calculator has an exponent method which the author did not include. If I were to include it, would it have higher precedence over everything except the End of Stream/EOS and the default option?
(If you have a better implementation of the Shunting Yard Algorithm, please suggest it!)
Those values are taken from precedence hierarchy in c from Data structures by Horowitz Sahni. Please check . You can enter your own numbers but in the priority order. For example
private static final int[] isp = {0, 3, 1, 1, 2, 2, 2, 0};
private static final int[] icp = {4, 3, 1, 1, 2, 2, 2, 0};
To add your power operator make following changes
lparen(0), rparen(1), plus(2), minus(3), divide(4), times(5), mod(6), eos(7), pow(8), operand(9) ;
// Giving ^ (custom power) operator more precedence (14) than other (+,-,*,/,%) operators
/** in stack precedence **/
private static final int[] isp = {0, 19, 12, 12, 13, 13, 13, 0, 14};
/** incoming character precedence **/
private static final int[] icp = {20, 19, 12, 12, 13, 13, 13, 0, 14};
/** operators **/
private static final char[] operators = {'(', ')', '+', '-', '/', '*', '%', ' ', '^'};
// ^ ^ typo with '{' and '}'
Add in switch
case '^' : return Precedence.pow;
Output :
Shunting Yard Algorithm Test
Enter infix expression
1+2*3^4/5-6%7
Postfix expression : 1234^*5/+67%-