The following is an algorithm that can convert an expression in infix notation to one in postfix, or RPN. Elsewhere on this site there are some algorithms that do the same thing using a binary tree, but the way I was taught to do it involves using a stack. This algorithm will work on any expression that uses simple binary operators and parenthesis, things get messy with unary operators or other non-binary ones. For this example, assume we're just using +, -, *, and /
To start with, assume we've got the infix expression in a string, and that we have a stack we're going to be using to help with the conversion. All we have to do is iterate through the string, checking each character, or token. There are four scenarios:
Operator: If the token is an operator, and there's nothing else on our stack, we push that operator onto the stack. If there is something on the stack, we compare the precedence of our current operator with the one on the stack, if the stack's is greater or equal to ours, we pop it and add it to our answer. If it's less than ours, we push our current operator and go on. We keep comparing the current operator to the stack untill we hit the end of the stack, we hit a left parenthesis on the stack, or we find an operator on the stack with lower precedence than ours.
Left Parenthesis: If the token is a left parenthesis we simply push it onto the stack.
Right Parenthesis: If the token is a right parenthesis, we do a Multi-Pop! That is to say, we pop everything off the stack untill we hit a left parenthesis or the end of the stack.
Operand: If the token is an operand we simply add it to our answer.
When all this is done with, we perform a Super-Pop!. Which means we pop every last thing off the stack. If everything went well, then the only things left should be operators. If there's a parenthesis left over, something’s wrong. If there’s an operand, you've pretty seriously fucked up, since at no point in the algorithm do we put those on the stack.
Now the answer should be the original expression, only in postfix. Go ahead and pat yourself and/or your computer on the back.
If you want the whole thing neatly done out in actual c++ code just look down. This example uses the apstring and apstack classes from the AP Computer Science course. They should be pretty self explanatory.
bool opGreaterEqual(char a, char b)
{
return (a=='*' || a=='/') >= (b=='*' || b=='/');
}
apstring infixToPostfix(apstring s)
{
int len=s.length();
char temp;
apstring ans="";
apstack<char> stack;
for(int i=0; i<len; i++)
{
if (s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/')
{
while( !stack.isEmpty() && stack.top()!='(' )
{
if ( opGreaterEqual(stack.top(), s[i]) )
{
stack.pop(temp);
ans+=temp;
}
else break;
}
stack.push(s[i]);
}
else if ( s[i]=='(' )
{
stack.push('(');
}
else if ( s[i]==')' )
{
while ( !stack.isEmpty() && stack.top()!='(' )
{
stack.pop(temp);
ans+=temp;
}
if ( !stack.isEmpty() ) stack.pop();
}
else if ( s[i]>='A' && s[i]<='Z' )
{
ans+=s[i];
}
}
while ( !stack.isEmpty() )
{
stack.pop(temp);
ans+=temp;
}
return ans;
}