dgbfs
BAN USERsplit the prefix into tokens and process those tokens one by one
use a stack
read a operator, push the token to the stack
read a non-operator, if the top element is operator, push the token to the stack otherwise, pop an element, which is the left operand, and another element, which is the operator, to construct an postfix expression, repeat it until the stack becomes empty or the top element is operator and then push the expression to the stack
pop the postfix expression and return it
public String prefixToPostfix(String prefix)
{
Stack<String> s = new Stack<String>();
String[] tokens = prefix.split(" ");
for(String token: tokens) {
if(isOperator(token)) {
s.push(token);
} else {
String operand = token;
while(!s.empty() && !isOperator(s.peek())) {
operand = s.pop() + " " + operand + " " + s.pop();
}
s.push(operand);
}
}
return s.pop();
}
private boolean isOperator(String s)
{
return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/");
}
Algorithm
group the string by unique characters
aabc =>(aa)(b)(c)
the substrings are either formed by the characters within same group or adjacent groups
each group alone forms n * (n-1)/2 unique substring (the group contains n characters)
adjacent groups form n * m unique substring (the groups contains m and n characters respectively)
Example
aabc
(3 + 1 + 1) + (2*1 + 1* 1) = 8
abc
(1 + 1 + 1) + (1*1 + 1*1) = 5
baaccb
(1 + 3 + 3 + 1) + (1*2 + 2*2 + 2*1) = 16
f(1) = 1
f(2) = 3
f(3) = 6
...
f(n) = n + f(n-1) = n*(n-1)/2
RepSpent high school summers donating toy monkeys in Minneapolis, MN. At the moment I'm building glue in Edison, NJ ...
0 1 2 3 4 5
- dgbfs November 08, 2012________________
0 | 0 0 0 1 0 0 |
1 | 0 [1] 0 1 0 1 |
2 | 0 0 0 0 0 0 |
3 | 0 1 0 [1] 0 1 |
4 |_ 0 1 1 0 1 1_|
There are two entities