Evaluation of Arithmetic Expression

This entry was posted in DATA STRUCTURE on by

Evaluation of Arithmetic Expression

An important application of stack is the compilation of arithmetic stack expressions in the programming languages.

The compiler must be able to translate the expression which is written in the usual notation known as infix notation to form a reverse polish notation.

compiler accomplish this task of notation conversion i.e infix to postfix with help of stack.

There are mainly three types of notations as follows:

1. Infix notation

2. postfix notation

3. prefix notation

 

Before discuss above three notation, you have to know about two main terms:

a) operator: to do any arithmetic operation or else i.e +,-,* etc.

b) operand: operand can be any number or alphabet i.e a , b or 8 ,7 etc.

 

Remember : operator is placed between operands. for example : a + b * c

 

Precedence and associativity table:

Priority Operator Precedence Associativity
1 Exponentiation ^ Highest Right Associative
2 Multiplication ( ∗ ) & Division ( / ) Second Highest Left Associative
3 Addition ( + ) & Subtraction ( − ) Lowest Left Associative

In case of bracket() used the it will be top highest.

.

 

Now , move to the notations:

  1. Infix Notation

In infix notation, operators are in between operands

for example: a + b

where a and b are two operands and operator + is placed between operands.

2. Postfix notation

In postfix notation, operators placed after operands

for example: a b +

3. Prefix notation

In prefix notation, operators placed before operands

for example : + a b

 

INFIX TO POSTFIX CONVERSION

There are two operations performed:

  1. pop: delete from stack
  2. push: add into stack

 

ALGORITHM INFIX TO POSTFIX CONVERSION

  1. Create a stack
  2. for each character ‘s’ in the input stream {
    • if (s is an operand)
      output s
    • else if (s is a right parentheses){
      POP and output tokens until a left parentheses is popped(but do not output)
      }
    • else {
      POP and output tokens until one of lower priority than s is encountered or a left parentheses is encountered
      or the stack is empty
      PUSH s
      }
  3. POP and output tokens until the stack is empty.

 

EXAMPLE:

For better understanding, let us trace out an example 1 * 2 – (3 + 4) + 5

INPUT CHARACTER OPERATION ON STACK STACK POSTFIX EXPRESSION
A   Empty 1
* Push * 1
B   * 12
– Check and Push – 12 *
( Push – ( 12 *
C   – ( 12 * 3
+ Check and Push – ( + 12 * 3
D   – ( + 12 * 34
) Pop and append to postfix till ‘(‘ – 12 * 34 +
+ Check and push + 12 * 34 + –
E   + 12 * 34 + – 5
End of Input Pop till Empty Empty 12 * 34 + – 5 +

we can also alphabets instead of numbers. suppose A=1,B=2,C=3,D=4 and E=5 then final POSTFIX Expression :- A B * C D + – E +

 

Algorithm To Convert Postfix Expression into Prefix Notation

  1. Scan the Postfix Expression from Left To Right.
  2. If the character is an Operand, then Push it on to the Stack.
  3. If the character is an Operator, then Pop Operand 1 and Operand 2 and concatenate them and Push the result on the Stack.
  4. Repeat the above steps until the Postfix Expression is scanned completely.
  5. To get the Prefix Expression, Pop the remaining elements of the Stack.

 

For example:

 7  6  $  5  * 5 – 1  7  /  9  9  +  /  +
Step 1:  Scanned character is a digit ‘7’.  So, push it into the stack.
|      |
|  7  |
+—–+
Step 2:  Scanned character is a digit ‘6’.  So, push it into the stack.
|  6  |
|  7  |
+—–+
Step 3:  Scanned character is an operator ‘$’.  Pop two elements from the stack and form a string containing the scanned operator and two popped elements.
 
$76
|      |
|      |
+—–+
Push the resultant string “$76” into the stack.
|        |
| $76  |
+——+
Step 4:  Scanned character is a digit ‘5’.  So, push it into the stack.
|  5    |
| $76  |
+——+
Step 5:  Scanned character is an operator ‘*’.  So, pop two elements from the stack and form  a string containing the scanned operator and two popped elements.  Then, push the resultant “*$765” string into the stack.
|          |
| *$765 |
+——–+
Step 6:  Scanned character is digit ‘5’.  Push it into the stack.
|    5     |
| *$765 |
+——–+
Step 7:  Scanned character is an operator ‘-‘.  Pop ‘5’ and “*$765” from the stack.  Form a string containing the scanned operator and two popped elements.  Push the resultant string into the stack
|              |
| -*$7655  |
+———–+
Step 8:  Scanned character is digit ‘1’.  Push it into the stack.
|      1      |
| -*$7655  |
+———–+
Step 9:  Scanned character is digit ‘7’.  Push it into the stack.
|      7       |
|      1       |
| -*$7655   |
+————+
Step 10:  Scanned character is an operator ‘/’.  Pop top two elements from the stack.  Form a string containing the scanned operator and two popped elements, push the resultant string into the stack.
|               |
|    /17      |
| -*$7655  |
+———–+
Step 11:  Scanned character is a digit ‘9’.  Push it into the stack.
|      9       | 
|    /17      |
| -*$7655   |
+————+
Step 12:  Scanned character is a digit ‘9’.  Push it into the stack.
|      9       |
|      9       | 
|    /17      |
| -*$7655   |
+————+
Step 13:  Scanned character is an operator ‘+’.  Pop top two elements from the stack.  Form a string containing the scanned operator and two popped elements, push the resultant string into the stack.
|              |
|   +99      | 
|    /17     |
| -*$7655  |
+———–+
Step 14:  Scanned character is an operator ‘/’.
|              | 
| //17+99  |
| -*$7655   |
+————+
Step 15:  Scanned character is an operator ‘+’.  Pop top two elements from the stack.  Form a string containing the scanned operator and two popped elements, push the resultant string into the stack.
|      |
|      |
+—–+
+ – * $ 7655//17+99
Resultant Prefix Expression: + – * $ 7655//17+99

 

 

Leave a comment