优先值在调车场算法实现中的意义

Question

我正在编写一个学习Java的计算器类。到目前为止，它可以处理简单的函数，如2+2, 2^2等，但我正试图实现分流场算法，以便它可以处理更复杂的表达式。

我是数据结构的新手，没有指南就无法编写这样的代码，所以经过研究，我在网上找到了几个例子，并在这里找到了其中一个。其他网站，如果你感兴趣的话:1,2。我选择了第一个链接网站，因为我最了解它。

但是我不明白作者在这里做什么:

/** 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};

我知道这与操作符的优先级有关，但我不确定这些数字是从哪里来的。有人能澄清一下吗?

此外，我的计算器有一个指数方法，作者没有包括。如果我要包含它，它会比流结束/EOS和默认选项有更高的优先级吗?

(如果你有更好的实现调车场算法，请建议!)

Answer 1

这些值取自Horowitz Sahni数据结构中的precedence hierarchy in c。请核对。您可以输入您自己的号码，但按优先顺序。例如

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};

要添加电源操作符，请进行以下更改

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 '}'

添加开关

case '^'  : return Precedence.pow;

输出:

Shunting Yard Algorithm Test
Enter infix expression
1+2*3^4/5-6%7
Postfix expression : 1234^*5/+67%-