Skip to content

Instantly share code, notes, and snippets.

@kanrourou
Created December 21, 2014 20:21
Show Gist options
  • Save kanrourou/4ed18411ea9cd8242885 to your computer and use it in GitHub Desktop.
Save kanrourou/4ed18411ea9cd8242885 to your computer and use it in GitHub Desktop.
//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