**Expressions, Conversion and Evaluation with C**

**(All you need to know about Expressions)**

In this tutorial, I will be writing in detail about an important programming concept i.e. Algebraic Expressions, different expression notations like Prefix, Postfix and Infix evaluation of the expressions, how to convert an expression from one notation to another and how to evaluate Algebraic Expressions using computers.

Each and every concept is backed by algorithms, illustrative examples and programs in C to help new programmers understand the concepts more clearly.

We will be using the concepts of Stacks and Binary Trees to convert and evaluate the expressions, so the reader is required to be clear with the fundamentals of these concepts.

**Topics covered by this tutorial:**

- What is an Algebraic Expression?
- What are different notations of representing expressions like Infix, Prefix, and Postfix?
- Why do we need different notations for the same expression?
- Why do we need to convert the expressions from one notation to another?
- How can we convert the expressions from one notation to another? (Algorithms, Programs, examples)
- Expression Trees
- How can we evaluate an expression? (Algorithm, Program)
- Reader's Exercise.

An algebraic expression is a legal combination of operands and operators. Operand is the quantity (unit of data) on which a mathematical operation is performed. Operand may be a variable like x, y, z or a constant like 5, 4,0,9,1 etc. Operator is a symbol which signifies a mathematical or logical operation between the operands. Example of familiar operators include +,-,*, /, ^ ( throughout the tutorial '^' will be referred to as Exponential Operator ) etc. Considering these definitions of operands and operators now we can write an example of expression as x+y*z. Note the phrase "LEGAL combination" in the definition of an Algebraic Expression, in aforementioned example of expression x+y*z, the operands x , y, z and the operators +,* form some legal combination. Take another example +xyz*, in this expression operators and operands do not make any LEGAL combination; this expression is not a valid algebraic expression.

An Algebraic Expression can be represented using three different notations:

Now, the obvious question that comes in our mind is, Why use these weird looking PREFIX and POSTFIX notations when we have a sweet and simple INFIX notation?

For example, will expression 3+5*4 evaluate to 32 i.e. (3+5)*4 or to 23 i.e. 3+(5*4). To solve this problem Precedence or Priority of the operators were defined. Operator precedence governs evaluation order. An operator with higher precedence is applied before an operator with lower precedence.

Following figure shows operator Precedence in descending order.

http://www.programmersheaven.com/articles/images/expressionprecedence.gif

Now, as we know the precedence of the operators, we can evaluate the expression 3+5*4 as 23. But wait, it doesn't end here what about the expression 6/3*2? Will this expression evaluate to 4 i.e. (6/3)*2 or to 1 i.e. 6/(3*2).As both * and the / have same priorities, to solve this conflict, we now need to use Associativity of the operators. Operator Associativity governs the evaluation order of the operators of same priority. For an operator with left-Associativity, evaluation is from left to right and for an operator with right-Associativity; evaluation is from right to left.

- , /, +, - have left Associativity. So the expression will evaluate to 4 and not 1.

Due to the above mentioned problem of considering operators' Priority and Associativity while evaluating an expression using infix notation, we use prefix and postfix notations. Both prefix and postfix notations have an advantage over infix that while evaluating an expression in prefix or postfix form we need not consider the Priority and Associativity of the operators. E.g. x/y*z becomes */xyz in prefix and xy/z* in postfix. Both prefix and postfix notations make Expression Evaluation a lot easier. (we will discuss this in detail, later in this tutorial)

But it is not easy to remember and manually write expressions in prefix or postfix form e.g. which one of following equations is easy to remember (x+y)/z*a (Infix) or xy+z/a* (Postfix)?

So, what is actually done is that the expression is scanned from the user in infix form; it is converted into prefix or postfix form and then evaluated without considering the parenthesis and priority of the operators.

Now let us move on the programming part, How to convert an expression from one notation to another? Well there are two ways to convert expression from one notation to another. First one uses

As there are 3 notations namely prefix, infix and postfix , there are a total of 6 conversions that can be done ,i.e. infix -> prefix, infix -> postfix, prefix -> infix, prefix -> postfix, postfix -> prefix, postfix -> infix. For the first 2 conversions we will be using stacks and for remaining 4 conversions we will be using Binary Expression Trees.

To convert an expression from infix to prefix and postfix, we are going to use stacks. Those who do not know what a stack is, here are a few words about it. A stack is a special type of data structure in which items are removed in reverse order from which they are added. Stack follows Last In First Out (LIFO) pattern. Adding an element to a stack is called PUSH and removing an item from a stack is called POP.

To convert an expression from infix to postfix, we are going to use a stack.

1) Examine the next element in the input.

2) If it is an operand, output it.

3) If it is opening parenthesis, push it on stack.

4) If it is an operator, then

i) If stack is empty, push operator on stack.

ii) If the top of the stack is opening parenthesis, push operator on stack.

iii) If it has higher priority than the top of stack, push operator on stack.

iv) Else pop the operator from the stack and output it, repeat step 4.

5) If it is a closing parenthesis, pop operators from the stack and output them until an opening parenthesis is encountered. pop and discard the opening parenthesis.

6) If there is more input go to step 1

7) If there is no more input, unstack the remaining operators to output.

Suppose we want to convert 2*3/(2-1)+5*(4-1) into Prefix form: Reversed Expression: )1-4(*5+)1-2(/3*2

Char Scanned | Stack Contents(Top on right) | Postfix Expression |

2 | Empty | 2 |

* | * | 2 |

3 | * | 23 |

/ | / | 23* |

( | /( | 23* |

2 | /( | 23*2 |

- | /(- | 23*2 |

1 | /(- | 23*21 |

) | / | 23*21- |

+ | + | 23*21-/ |

5 | + | 23*21-/5 |

* | +* | 23*21-/5 |

( | +*( | 23*21-/5 |

4 | +*( | 23*21-/54 |

- | +*(- | 23*21-/54 |

1 | +*(- | 23*21-/541 |

) | +* | 23*21-/541- |

Empty | 23*21-/541-*+ |

So, the Postfix Expression is 23*21-/541-*+

Refer program #1 for infix to postfix Conversion

It is a bit trickier algorithm, in this algorithm we first reverse the input expression so that a+b*c will become c*b+a and then we do the conversion and then again the output string is reversed. Doing this has an advantage that except for some minor modifications the algorithm for Infix->Prefix remains almost same as the one for Infix->Postfix.

1) Reverse the input string.

2) Examine the next element in the input.

3) If it is operand, add it to output string.

4) If it is Closing parenthesis, push it on stack.

5) If it is an operator, then

i) If stack is empty, push operator on stack.

ii) If the top of stack is closing parenthesis, push operator on stack.

iii) If it has same or higher priority than the top of stack, push operator on stack.

iv) Else pop the operator from the stack and add it to output string, repeat step 5.

6) If it is a opening parenthesis, pop operators from stack and add them to output string until a closing parenthesis is encountered. Pop and discard the closing parenthesis.

7) If there is more input go to step 2

8) If there is no more input, unstack the remaining operators and add them to output string.

9) Reverse the output string.

Suppose we want to convert 2*3/(2-1)+5*(4-1) into Prefix form: Reversed Expression: )1-4(*5+)1-2(/3*2

Char Scanned | Stack Contents(Top on right) | Prefix Expression(right to left) |

) | ) | |

1 | ) | 1 |

- | )- | 1 |

4 | )- | 14 |

( | Empty | 14- |

* | * | 14- |

5 | * | 14-5 |

+ | + | 14-5* |

) | +) | 14-5* |

1 | +) | 14-5*1 |

- | +)- | 14-5*1 |

2 | +)- | 14-5*12 |

( | + | 14-5*12- |

/ | +/ | 14-5*12- |

3 | +/ | 14-5*12-3 |

* | +/* | 14-5*12-3 |

2 | +/* | 14-5*12-32 |

Empty | 14-5*12-32*/+ |

Reverse the output string : +/*23-21*5-41 So, the final Prefix Expression is +/*23-21*5-41

Refer program #1 For infix to prefix Conversion.

All the remaining conversions can easily be done using a Binary Expressions Tree. In fact the above 2 conversions, viz Infix-> Prefix and Infix -> Postfix, can also be done using Binary Expression Trees but that is a very tricky thing and stacks can be used to handle the conversions easily. Now we will move a step ahead and define a Binary Expression Tree.

An Expression Tree is a strictly binary tree in which leaf nodes contain Operands and non-leaf nodes contain Operator, root node contain the operator that is applied to result of left and right sub trees. Once we obtain the Expression Tree for a particular expression, its conversion into different notations (infix, prefix, and postfix) and evaluation become a matter of Traversing the Expression Tree. The following Figure shows an expression tree for above expression 2*3/(2-1)+5*(4-1)

http://www.programmersheaven.com/articles/images/expressionnode.gif

http://www.programmersheaven.com/articles/images/expressionexptree.gif

When we run Pre-order traversal (visit root, left child and then right child) on the Binary Expression Tree we get prefix notation of the expression, similarly an Post-order traversal (visit left child, right child and then root) will yield postfix notation. What will we get from an in-order Traversal (visit left child, root and then right child)? Well, for the expressions which do not contain parenthesis, in-order traversal will definitely give infix notation of expression but expressions whose infix form requires parenthesis to override conventional precedence of operators can not be retrieved by simple in-order traversal.

The following algorithm works for the expressions whose infix form does not require parenthesis to override conventional precedence of operators. 1) Create the Expression Tree from the prefix expression

2) Run in-order traversal on the tree.

1) Create the Expression Tree from the prefix expression

2) Run post-order traversal on the tree.

Well you see how easy it is! Most important point here is to create Expression tree from Prefix expression, following algorithm does that for you:

1) Reverse the prefix expression

2) Examine the next element in the input.

3) If it is operand then

i) create a leaf node i.e. node having no child (node- >left_child=node->right_child=NULL)

ii) copy the operand in data part

iii) PUSH node's address on stack

4) If it is an operator, then

i) create a node

ii) copy the operator in data part

iii) POP address of node from stack and assign it to node->left_child

iv) POP address of node from stack and assign it to node->right_child

v) PUSH node's address on stack

5) If there is more input go to step 2

6) If there is no more input, POP the address from stack, which is the address of the ROOT node of Expression Tree.

Refer program #2 For prefix to infix and postfix conversion.

The following algorithm works for the expressions whose infix form does not require parenthesis to override conventional precedence of operators. 1) Create the Expression Tree from the postfix expression 2) Run in-order traversal on the tree.

1) Create the Expression Tree from the postfix expression 2) Run pre-order traversal on the tree.

1) Examine the next element in the input.

2) If it is operand then

i) create a leaf node i.e. node having no child (node->left_child=node->left_child=NULL)

ii) copy the operand in data part

iii) PUSH node's address on stack

3) If it is an operator, then

i) create a node

ii) copy the operator in data part

iii) POP address of node from stack and assign it to node->right_child

iv) POP address of node from stack and assign it to node->left_child

v) PUSH node's address on stack

4) If there is more input go to step 1

5) If there is no more input, POP the address from stack, which is the address of the ROOT node of Expression Tree.

Refer program #2 For postfix to infix and prefix conversion.

Well, at last we are done with converting the expressions from one type to another. As a summary here is what we have done so far : 1) Infix -> Prefix using stack

2) Infix -> Postfix using stack

3) Prefix -> Infix using Expression Trees

4) Prefix -> Postfix using Expression Trees

5) Postfix -> Infix using Expression Trees

6) Postfix -> Prefix using Expression Trees

Now all we are left with is Evaluating an Expression. Evaluating an expression involves two phases: 1) Create an expression tree for given expression

2) Evaluate the tree recursively

We already know how to create an expression tree for prefix and postfix notations. Algorithm for creating Expression Tree from Infix expression is left as reader exercise and some help can be found at http://www.seas.gwu.edu/~csci131/fall96/exp_to_tree.html

Following procedure will evaluate an expression tree in a recursive fashion:

```
IF root != NULL
IF current node contains an operator
x = Evaluate Tree(root -> left_child)
y = Evaluate Tree(root -> right_child)
Perform operation on x and y, specified by the
operator and store result in z
Return z
else Return root->data
```

Refer program #2 for evaluation of an Expression Tree.

© Nachum Danzig January 2004