1
$\begingroup$

Table 4 in Problem Solving with Algorithms and Data Structures's chapter on Infix, Prefix and Postfix Expressions gives the following examples:

Infix Expression: A + B * C + D 
Prefix Expression: + + A * B C D
Postfix Expression: A B C * + D +

Why is prefix not:

+ A + * B C D

To show my reason for this question, I'll use lowercase characters combined to represent a completed operation (e.g. + A B becomes ab). Here's my thinking:

+ A + * B C D 
+ A + bc D
+ A bcd
abcd

Here's my thinking applied to the answer supplied by the text:

+ + A * B C D
+ + A bc D
+ abc D
abcd

They both work?

I'm making the same mistake with

Infix Expression: A + B + C + D 
Prefix Expression: + + + A B C D    
Postfix Expression: A B + C + D +

I write postfix as:

A B C D + + +

...which is wrong (but I don't know why).

$\endgroup$
  • 1
    $\begingroup$ Yours and the textbook answer are mathematically equivalent. $\endgroup$ – Raphael Jan 7 '16 at 13:52
  • 2
    $\begingroup$ @Raphael No they are not. Think floating point numbers. $\endgroup$ – Yuval Filmus Jan 7 '16 at 23:01
  • $\begingroup$ @YuvalFilmus Since floating point numbers are not what I would call "mathematical", I think my statement is correct. In the usual (associative, commutative) rings and fields we use in mathematics, these statements are equivalent. In programming resp. numerical investigations, the terms are different, true. That's worthwhile to note, thanks. $\endgroup$ – Raphael Jan 8 '16 at 9:31
2
$\begingroup$

What you're missing is the associativity of operators. All operators you mention in your examples are binary. An expression of the form $A + B + C + D$ is interpreted by the parser as $(((A+B)+C)+D)$. When converting such a fully parenthesized expression into prefix form, we apply the rule $(\alpha + \beta) \to +\alpha\beta$. Denote this transformation by $T$. Then $$ T[(((A+B)+C)+D)] = +T[((A+B)+C)]D = ++T[(A+B)]CD = +++ABCD. $$ In a completely analogous way, the operator $S$ converting into postfix makes the transformation $S[(\alpha+\beta)] = \alpha\beta+$: $$ S[(((A+B)+C)+D)] = S[((A+B)+C)]D+ = S[(A+B)]C+D+ = AB+C+D+. $$

The operator $+$ is associative, but imagine what happens with an operator like $-$. The expression $A-B-C$ is interpreted as $((A-B)-C)$, and its prefix and postfix forms are $--ABC$ and $AB-C-$, respectively. Any other conversion would result in an arithmetically inequivalent expression. That's why associativity matters.

Most operators associate to the left, just like $+$. Exponentiation traditionally associates to the right.

On top of this, we also have operator precedence, which leads to the parsing of $A+B*C+D$ as $((A+(B*C))+D)$. If you apply the transformations $T$ and $S$ you will get the expressions given in the book.

$\endgroup$
2
$\begingroup$

Yes in this case they both happen to equal the same value however yours is technically wrong. Your forgetting the final rule of order of operations which is left-to-right.

A + B * C + D

(mult. first)

A + *bc + D

(left addition second)

+a *bc + D

(finally convert the last addition)

++a*bcd

What you posted + A + * B C D corresponds instead to A + (B*C + D)

$\endgroup$
1
$\begingroup$

Ever heard of Tree traversals? I suggest you not to bang your head playing with expressions. Just construct a parse tree and perform

  • In order traversal for infix notation - L A R
  • Pre order traversal for prefix notation - A L R
  • Post order traversal for postfix notation - L R A

where L = left child, R = Right child and A = parent. (See also Depth First Traversals)

The concept has something to do with removing ambiguity while deriving the parse tree. The expression A + B + C + D could have multiple parse trees, two of which are presented below.

  +                 +
 / \               / \
A   +             +   D
   / \           / \
  B   +         +   C
     / \       / \
    C   D     A   B

Left side tree's postorder ( L R A ) traversal gives your answer i.e. A B C D + + +, but the right tree's gives A B + C + D + and luckily both are correct. Why? Since all the three operators have same precedence and associativity doesn't matter for addition operator +. What if, the expression is A + B * C - D? Which is correct? This A B C D - * + or this A B C * + D -? So, you need to consider the precedence and associativity of the operators while constructing parse trees to generate unambiguous parse trees.

Rules:

  • For right associative operators (of same precedence) right recursive trees are generated, i.e. the tree grows towards right (left tree above fig) and right most operator is evaluated first.

  • For left associative operators (of same precedence) left recursive trees are generated, i.e. the tree grows towards left (right tree above fig) and left most operator is evaluated first.

  • The level of the operator with higher precedence must be lower in the tree than the level of the operator with lower precedence i.e. an operator with higher precedence is evaluated first and result is passed to the parent (in tree).

For the expression A + B * C,

  +              *
 / \            / \
A   *          +   C
   / \        / \
  B   C      A   B

left tree is correct, as the level of * is lower and right tree is wrong.

In order to reflect normal usage, addition, subtraction, multiplication, and division operators are usually left-associative while an exponentiation operator (if present) is right-associative. Source

See also Operator-precedence parser and Shunting Yard Algo by Dijkstra and an example considering precedence. Also, the precedence and associativity of operators in C++.

See also More examples of Infix, Postfix and Prefix conversions, making of parse tree (jump to the end of the page).

$\endgroup$
  • $\begingroup$ Credits to Yuval Filmus, for his answer, from which I got the idea about associativity. $\endgroup$ – azam Jan 10 '16 at 5:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.