Tuesday, November 5, 2013

Recreator – Parentheses (Binary Operators)

Parentheses are removed from expressions during translation.  The binary operator recreate function needs to recreate the parentheses for operators depending on their precedences.  Consider these expressions with their translations:
A * B + C * D          (A + B) * (C + D)
A B * C D * +          A B + C D + *
The translations of these two expressions have a similar form.  The first expression will be recreated correctly since multiply is higher precedence than add.  However the second expression without parentheses "A + B * C + D" does not mean the same thing since add is lower precedence than multiply making the parentheses required.

Parentheses are required around an operand if the precedence of the operator is higher than the operand. Parentheses are also required around the second operand if the precedence of the operator is the same as the operand since operators of the same precedence are processed from left to right.

Implementation

A precedence variable was added the stack item to hold the precedence of an operator sub-expression.  The push access function was modified to take an optional precedence value that is pushed with the string.  The default precedence is set to the highest precedence for when operands like constants and variables are pushed.  A top access function was added so that the item on top of the string holding stack can be accessed.
A new pop with parentheses access function was added that takes a flag argument, which when set will surround the string operand popped from the string holding stack with parentheses when set.

The binary operator recreate function was modified to get the precedence of the operator being processed from the table.  The pop call of the second operand was replaced with a call to the new pop with parentheses with the argument set to whether the operator precedence is higher than or the same as the precedence of the item on top of the stack.  Similarly the first operand is popped with parentheses if the operator precedence is higher than the top item.

Instead of using the top append access function, the string of the operator expression is built in a local string.  The string is first set to the second operand with parentheses if needed.  The string is then set to first operand with parentheses if needed, plus a space, plus the operator name, plus another space plus the current value of the string with the second operand.  Finally this string is pushed to the string holding stack with the precedence of the operator.

The expected outputs for expression test #2 (parenthetical expressions) were set to the inputs.  Many of these expressions match the inputs since the precedence for binary operator is now being handled.  The expressions that don't match involve unary operators (no precedence checking yet) and unnecessary entered parentheses.

[commit 694e224aee]

No comments:

Post a Comment

All comments and feedback welcomed, whether positive or negative.
(Anonymous comments are allowed, but comments with URL links or unrelated comments will be removed.)