今�Hの国の呵呵君: [Algorithm]Convert Expression to Reverse Polish Notation
在Evaluate Reverse Polish Notation中讨论过这个问题，普通式子转换成逆波兰式就要注意两点：第一，由于涉及的运算符都是双目的（不包括括号），运算符要放在第二个操作数后面；第二， 如果第二个操作数，由于运算符号的优先性，是一个表达式，就先写出表示第二个操作数的逆波兰式，之后加上操作符。我们这里讨论的式子涉及普通的加减乘除，和左括号和右括号。值得注意的是，括号只是决定运算的优先顺序，所以不会出现在我们最后的逆波兰式当中。根据以上两个要点，先写出转换成逆波兰式的算法，之后再来分别解释，首先维护两个栈，第一个栈只存操作符，第二个栈是存逆波兰式的结果，第一个栈中我们先压入'#'并认为它的优先级最低（这一步可以让我们避免check栈空的情况）：
- 如果遇到的是操作数，直接压入栈2，操作数的顺序在逆波兰式和原中缀表达式中是一样的
- 如果遇到的是操作符：
- 如果是'+'：
- 如果栈1顶是'('，直接入栈1
- 否则，依次弹出所有优先级大于等于它的运算符并压入栈2，直到遇见'('或者'#'，然后入栈1
- 如果是'-'：
- 如果栈1顶是'('，直接入栈1
- 否则，依次弹出所有优先级大于等于它的运算符并压入栈2，直到遇见'('或者'#'，然后入栈1
- 如果是'*'：
- 如果栈1顶是'('，直接入栈1
- 否则，依次弹出所有优先级等于它的运算符（没有比*优先级更高的（不考虑括号））并压入栈2，直到遇见'('或者'#'，然后入栈1
- 如果是'/'：
- 如果栈1顶是'('，直接入栈1
- 否则，依次弹出所有优先级等于它的运算符（没有比/优先级更高的（不考虑括号））并压入栈2，直到遇见'('或者'#'，然后入栈1
- 如果是'('，直接入栈1
- 如果是')'，弹出所有'('和')'之间的操作符并压入栈2 ，抛弃栈1里的'('
- 结尾的时候栈1不为空，依次弹出压入栈2
主要解释操作符的部分，首先如果不考虑括号的话，为了遵循转换的俩个要点。当碰到的运算符是+或者-时，如果栈1里存在除了#以外的运算符，由于优先级高的先算并且优先级相同的是从左向右算，说明栈里所有的运算符的第二个操作数，或者第二个操作数的表达式已经有了，不会受到现在要压入栈的操作符的影响，所以可以依次出栈并且压入栈2。同理，如果是*后者/的话，遵循的原则是相同的，若果栈里有优先级一样的，全部弹出，依次压入栈2。考虑有括号的情况，括号里面的内容就是一个要率先evaluate的表达式，evaluate括号里面的表达式（多个括号的情况，总会有不含括号的表达式），就和evaluate不带括号的表达式又是一样的了。我们要做的就是设定一个边界，就是左括号和右括号的作用。有了括号后。处理+-*/的方式只需要做小小的改变，如果栈1顶端是'('视为跟空的一样，直接入栈。出栈1时，碰到'('就停止。这样的操作对原来就在栈1里面的操作符也不会有影响，因为括号的优先级是最高的，需要先算出括号里面的值当成第二个操作数，栈1里面的运算符才可以出栈。
Read full article from 今�Hの国の呵呵君: [Algorithm]Convert Expression to Reverse Polish Notation
No comments:
Post a Comment