Postfix to infix, part 2: adding the parentheses : Algorithms for the masses

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)

Tue 15-Nov-2011 3:35 PM Blog / tags: expression postfix infix rpn

Loading links to posts on similar topics...

previous post next post

No Responses

Feel free to add a comment...

Leave a response

Note: some MarkDown is allowed, but HTML is not. Expand to show what's available.

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...

by Julian M Bucknall