Evaluation of Expressions

EVALUATION OF EXPRESSIONS
The way to write arithmetic expression is known as a notation. An arithmetic

expression can be written in three different but equivalent notations, i.e., without
changing the essence or output of an expression. These notations are −
 Infix Notation
 Prefix (Polish) Notation
 Postfix (Reverse-Polish) Notation
Infix Notation
 We write expression in infix notation, e.g. a - b + c, where operators are used in-
between operands. It is easy for us humans to read, write, and speak in infix
notation but the same does not go well with computing devices. An algorithm to
process infix notation could be difficult and costly in terms of time and space
consumption.
Prefix Notation
 In this notation, operator is prefixed to operands, i.e. operator is written ahead of
operands. For example, +ab. This is equivalent to its infix notation a + b. Prefix
notation is also known as Polish Notation.
Postfix Notation
 This notation style is known as Reversed Polish Notation. In this notation style,
the operator is postfixed to the operands i.e., the operator is written after the
operands. For example, ab+. This is equivalent to its infix notation a + b.
 The following table briefly tries to show the difference in all three notations –
Sr.No. Infix Notation Prefix Notation Postfix Notation
1 a+b +ab ab+
2 (a + b) ∗ c ∗+abc ab+c∗
3 a ∗ (b + c) ∗a+bc abc+∗
4 a/b+c/d +/ab/cd ab/cd/+
5 (a + b) ∗ (c + d) ∗+ab+cd ab+cd+∗
6 ((a + b) ∗ c) - d -∗+abcd ab+c∗d-
Parsing Expressions
As we have discussed, it is not a very efficient way to design an algorithm or program to
parse infix notations. Instead, these infix notations are first converted into either postfix
or prefix notations and then computed.
To parse any arithmetic expression, we need to take care of operator precedence and
associativity also.
Precedence
When an operand is in between two different operators, which operator will take the
operand first, is decided by the precedence of an operator over others. For example −
As multiplication operation has precedence over addition, b * c will be evaluated first. A

table of operator precedence is provided later.
Associativity
Associativity describes the rule where operators with the same precedence appear in an
expression. For example, in expression a + b − c, both + and – have the same
precedence, then which part of the expression will be evaluated first, is determined by
associativity of those operators. Here, both + and − are left associative, so the
expression will be evaluated as (a + b) − c.
Precedence and associativity determines the order of evaluation of an expression.

Following is an operator precedence and associativity table (highest to lowest) –
Sr.No. Operator Precedence Associativity
1 Exponentiation ^ Highest Right Associative
2 Multiplication ( ∗ ) & Division ( / ) Second Highest Left Associative
3 Addition ( + ) & Subtraction ( − ) Lowest Left Associative
The above table shows the default behavior of operators. At any point of time in
expression evaluation, the order can be altered by using parenthesis. For example −
In a + b*c, the expression part b*c will be evaluated first, with multiplication as
precedence over addition. We here use parenthesis for a + b to be evaluated first,
like (a + b)*c.
Postfix Evaluation Algorithm

We shall now look at the algorithm on how to evaluate postfix notation −
Step 1 − scan the expression from left to right

Step 2 − if it is an operand push it to stack
Step 3 − if it is an operator pull operand from stack and perform operation
Step 4 − store the output of step 3, back to stack
Step 5 − scan the expression until all operands are consumed
Step 6 − pop the stack and perform operation
How to convert an Infix expression to a Postfix

expression?
To convert infix expression to postfix expression, use the stack data structure.
Scan the infix expression from left to right. Whenever we get an operand, add it
to the postfix expression and if we get an operator or parenthesis add it to the
stack by maintaining their precedence.
Consider the infix expression exp = “a+b*c+d”

and the infix expression is scanned using the iterator i, which is initialized as i =
0.
1st Step: Here i = 0 and exp[i] = ‘a’ i.e., an operand. So add this in the postfix
expression. Therefore, postfix = “a”.
2nd Step: Here i = 1 and exp[i] = ‘+’ i.e., an operator. Push this into the
stack. postfix = “a” and stack = {+}.
3rd Step: Now i = 2 and exp[i] = ‘b’ i.e., an operand. So add this in the postfix
expression. postfix = “ab” and stack = {+}.
4th Step: Now i = 3 and exp[i] = ‘*’ i.e., an operator. Push this into the
stack. postfix = “ab” and stack = {+, *}.
5th Step: Now i = 4 and exp[i] = ‘c’ i.e., an operand. Add this in the postfix
expression. postfix = “abc” and stack = {+, *}.
6th Step: Now i = 5 and exp[i] = ‘+’ i.e., an operator. The topmost element of
the stack has higher precedence. So pop until the stack becomes empty or the
top element has less precedence. ‘*’ is popped and added in postfix. So postfix
= “abc*” and stack = {+}.
Now top element is ‘+‘ that also doesn’t have less precedence. Pop it. postfix =
“abc*+”.
Now stack is empty. So push ‘+’ in the stack. stack = {+}.
7th Step: Now i = 6 and exp[i] = ‘d’ i.e., an operand. Add this in the postfix
expression. postfix = “abc*+d”.
Final Step: Now no element is left. So empty the stack and add it in the postfix
expression. postfix = “abc*+d+”.

Evaluation of Expressions

Uploaded by

Copyright:

Available Formats

Evaluation of Expressions

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Evaluation of Expressions

Uploaded by

Copyright:

Available Formats

EVALUATION OF EXPRESSIONS

The way to write arithmetic expression is known as a notation. An arithmetic

1 a+b +ab ab+

4 a/b+c/d +/ab/cd ab/cd/+

6 ((a + b) ∗ c) - d -∗+abcd ab+c∗d-

As multiplication operation has precedence over addition, b * c will be evaluated first. A

Precedence and associativity determines the order of evaluation of an expression.

Sr.No. Operator Precedence Associativity

1 Exponentiation ^ Highest Right Associative

2 Multiplication ( ∗ ) & Division ( / ) Second Highest Left Associative

3 Addition ( + ) & Subtraction ( − ) Lowest Left Associative

Postfix Evaluation Algorithm

Step 1 − scan the expression from left to right

How to convert an Infix expression to a Postfix

Consider the infix expression exp = “a+b*c+d”

Now stack is empty. So push ‘+’ in the stack. stack = {+}.

You might also like