Monday, December 22, 2014

[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里面的运算符才可以出栈。

代码如下:
//input: expression string, there may be multiple spaces
//return: reverse polish notation string with one space between each element
class Solution {
public String convertToReversePolish(String exp) {
if (exp == null)
return null;
String res = "";
int len = exp.length();
Stack<Character> operator = new Stack<Character>();
Stack<String> reversePolish = new Stack<String>();
//avoid checking empty
operator.push('#');
for (int i = 0; i < len;) {
//deal with space
while (i < len && exp.charAt(i) == ' ')
i++;
if (i == len)
break;
//if is number
if (isNum(exp.charAt(i))) {
String num = "";
while (i < len && isNum(exp.charAt(i)))
num += exp.charAt(i++);
reversePolish.push(num);
//is operator
} else if (isOperator(exp.charAt(i))) {
char op = exp.charAt(i);
switch (op) {
case '(':
operator.push(op);
break;
case ')':
while (operator.peek() != '(')
reversePolish.push(Character.toString(operator.pop()));
operator.pop();
break;
case '+':
case '-':
if (operator.peek() == '(')
operator.push(op);
else {
while (operator.peek() != '#' && operator.peek() != '(')
reversePolish.push(Character.toString(operator.pop()));
operator.push(op);
}
break;
case '*':
case '/':
if (operator.peek() == '(')
operator.push(op);
else {
while (operator.peek() != '#' && operator.peek() != '+' &&
operator.peek() != '-' && operator.peek() != '(')
reversePolish.push(Character.toString(operator.pop()));
operator.push(op);
}
break;
}
i++;
}
}
while (operator.peek() != '#')
reversePolish.push(Character.toString(operator.pop()));
while (!reversePolish.isEmpty())
res = res.length() == 0? reversePolish.pop() + res: reversePolish.pop() + " " + res;
return res;
}
public boolean isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')';
}
public boolean isNum(char c) {
return c - '0' >= 0 && c - '0' <= 9;
}
}




No comments:

Post a Comment