Created
December 21, 2014 20:21
-
-
Save kanrourou/4ed18411ea9cd8242885 to your computer and use it in GitHub Desktop.
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; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment