Postfix to infix, part 2: adding the parentheses

Once upon a time (all right, it was in May 2010), I wrote an article for PCPlus about generating all possible arithmetic operations with the standard four operators. You can read the article here. After I’d written it, I wrote a blog post about how easy it was to convert the RPN form (Reverse Polish Notation) of the expressions I was generating into the standard algebraic or infix form. You can read that post here. (Note that this post will make more sense if you read these two articles first to get some background.)

Unfortunately, there was a bug in the pseudo-code I’d written for that latter post. If you’d started with an RPN expression like 2 3 4 ÷ ÷, you’d get the following infix expression: 2 ÷ 3 ÷ 4. Unfortunately, if you evaluate the RPN expression you get 8/3 but if you evaluate the algebraic expression you’d get 1/6. What went wrong?

The problem is that we’re missing some parentheses. In the absence of parentheses, a series of equal-precedence operators is evaluated from left to right. My example RPN expression comes from a tree that looks like this:

So the RPN expression should be converted to 2 ÷ (3 ÷ 4). Instead we are converting it to an implicit (2 ÷ 3) ÷ 4, which is a very different tree:

The problem then is the left-associativity of operators when they have the same precedence, and only when they are subtract or divide (the left-associativity problem doesn’t matter with add and multiply). Looking at the tree images above, this is only a problem when we have a right child whose operator is the same as this node’s operator and is either - or ÷. So we must do something slightly different when we recursively visit the right child than we do with the left child.

Here’s my original pseudo-code:

string Visit(node, priorPrecedence) {
if node is number
return number.ToString()
result = Visit(node.left, node.precedence) +
node.operator +
Visit(node.right, node.precedence)
if node.precedence < priorPrecedence
result = '(' + result + ')'
return result
}

Since we have to do something different about parentheses if we visit left than we do if we visit right, we might as well bring that decision up into the code that operates on the current node instead. In the following pseudo-code I make use of two helper routines, one to determine if we need parentheses for the left child and the other similarly for the right child.

boolean NeedParensOnLeft(node) {
return (node.left is operator) and
(node.left.precedence < node.precedence)
}

boolean NeedParensOnRight(node) {
if node.right is number
return false
if node.operator is '+' or node.operator is '*'
return (node.right.precedence < node.precedence)
return (node.right.precedence <= node.precedence)
}

string Visit(node) {
if node is number
return number.ToString()

lhs = Visit(node.left)
if NeedParensOnLeft(node)
lhs = '(' + lhs + ')'

rhs = Visit(node.right)
if NeedParensOnRight(node)
rhs = '(' + rhs + ')'

return lhs + node.operator + rhs
}

For grins (and to make sure I had got it right this time), here’s some complete JavaScript code to convert an RPN expression to a properly-parenthesized algebraic expression. It first converts the RPN expression into an expression tree, and then reads that tree to produce an infix expression as discussed above:

var makeNumberNode = function (number) {
return {
kind  : "number",
value : number
};
};

var makeOpNode = function (op, left, right) {
var precedence = 1;
if ((op === "*") || (op === "/")) {
precedence = 2;
}
return {
kind       : "operator",
operator   : op,
precedence : precedence,
left       : left,
right      : right
};
};

var convertRPN2Tree = function (rpnExpr) {
var stack = [],
i,
ch,
rhs,
lhs;

for (i = 0; i < rpnExpr.length; i++) {
ch = rpnExpr.charAt(i);
if ((ch >= "0") && (ch <= "9")) {
stack.push(makeNumberNode(ch));
}
else {
rhs = stack.pop();
lhs = stack.pop();
stack.push(makeOpNode(ch, lhs, rhs));
}
}

return stack.pop();
};

var needParensOnLeft = function (node) {
return ((node.left.kind === "operator") &&
(node.left.precedence < node.precedence));
};

var needParensOnRight = function (node) {
if (node.right.kind === "number") {
return false;
}
if ((node.operator === "+") || (node.operator === "*")) {
return (node.right.precedence < node.precedence);
}
return (node.right.precedence <= node.precedence);
};

var visit = function (node) {
if (node.kind === "number") {
return node.value;
}

var lhs = visit(node.left);
if (needParensOnLeft(node)) {
lhs = '(' + lhs + ')';
}

var rhs = visit(node.right);
if (needParensOnRight(node)) {
rhs = '(' + rhs + ')';
}

return lhs + node.operator + rhs;
};

var convertRPN2Infix = function (rpnExpr) {
var tree = convertRPN2Tree(rpnExpr);
var infixExpr = visit(tree);
alert(rpnExpr + " ==> " + infixExpr);
};

convertRPN2Infix("234//"); // => 2/(3/4)
convertRPN2Infix("23/4/"); // => 2/3/4
convertRPN2Infix("234**"); // => 2*3*4
convertRPN2Infix("23*4*"); // => 2*3*4

(A couple of notes are in order. First I made the RPN expression deliberately simple; it is assumed to contain only single-digit numbers. Second there is no error-checking at all: don’t pass in invalid RPN expressions. Third, I made sure the code passes JSLint; you should also do this as a matter of course. Oh, that makes three notes, oh well.)

Now playing:
Eastern Sun - World Soul
(from In Emptiness)

No Responses

Feel free to add a comment...

Leave a Response

Some MarkDown is allowed, but HTML is not. (Click to learn more.)

• Emphasize with italics: surround word with underscores _emphasis_
• Emphasize strongly: surround word with double-asterisks **strong**
• Link: surround text with square brackets, url with parentheses [text](url)
• Inline code: surround text with backticks IEnumerable
• Unordered list: start each line with an asterisk, space * an item
• Ordered list: start each line with a digit, period, space 1. an item
• Insert code block: start each line with four spaces
• Insert blockquote: start each line with right-angle-bracket, space > Now is the time...

Extras

Search

I'm Julian M Bucknall, an ex-pat Brit living in Colorado, an atheist, a microbrew enthusiast, a Volvo 1800S owner, a Pet Shop Boys fanboy, a slide rule and HP calculator collector, an amateur photographer, a Altoids muncher.

DevExpress

I'm Chief Technology Officer at Developer Express, a software company that writes some great controls and tools for .NET and Delphi. I'm responsible for the technology oversight and vision of the company.

Archives

September 2015 (0)
SMTWTFS
« Aug
12345
6789101112
13141516171819
20212223242526
27282930