我们这里讨论的式子涉及普通的加减乘除,和左括号和右括号。值得注意的是,括号只是决定运算的优先顺序,所以不会出现在我们最后的逆波兰式当中。根据以上两个要点,先写出转换成逆波兰式的算法,之后再来分别解释,首先维护两个栈,第一个栈只存操作符,第二个栈是存逆波兰式的结果,第一个栈中我们先压入'#'并认为它的优先级最低(这一步可以让我们避免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里面的运算符才可以出栈。
代码如下:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//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