CS13002 Programming and Data Structures, Spring 2002--2003
(SECTION 1/A)

LAB TEST 3

For students with odd PC numbers


[Evaluation of arithmetic expressions in prefix notation]

In the usual infix notation for writing arithmetic expressions one writes the operator between the two operands, as in a+b or ((a+b)*c)/d-(c*b). In the prefix notation one writes the operator first and then the operands (the first and the second in that order). Some examples are given below: 

infix                        prefix
a                         a
a+b                       +ab
(a+b)*c                   *+abc
((a+b)*c)/d               /*+abcd
((a+b)*c)/d-(e*f)         -/*+abcd*ef
(((a-5)*c+3)/2)-(a-8*c)   -/+*-a5c32-a*8c
Irrespective of the precedence of the operators the prefix notation does not require brackets. For example, the infix expression a-8*c is interpreted as a-(8*c) and not as (a-8)*c. This is because the operator * has more binding capacity than - and hence binds (the common operand) 8 more tightly than - does. But the prefix notations for a-(8*c) and (a-8)*c are different, namely -a*8c and *-a8c.

Given a prefix expression the corresponding (bracketed) infix expression can be obtained using a stack. Start with an initially empty stack and then loop:

Read the input string backwards (from end to beginning) character-by-character. If a non-operator (a digit or a variable) is read, push it to the stack. If an operator is read, pop the stack twice, apply the operation on the two popped entries and push the result back to the stack.

If the input is a proper prefix expression, the stack contains the corresponding infix expression at the top of the stack (which should also be the bottom of the stack), after the entire input is read. The following examples illustrate this algorithm. Here the stack grows towards left. 

Input 1: -/*+abcd*cb

Read  Operator  Stack operation          Stack content
b        No         push                                  b
c        No         push                                c,b
*        Yes     pop,pop,push                         (c*b)
d        No         push                            d,(c*b)
c        No         push                          c,d,(c*b)
b        No         push                        b,c,d,(c*b)
a        No         push                      a,b,c,d,(c*b)
+        Yes     pop,pop,push               (a+b),c,d,(c*b)
*        Yes     pop,pop,push             ((a+b)*c),d,(c*b)
/        Yes     pop,pop,push           (((a+b)*c)/d),(c*b)
-        Yes     pop,pop,push         ((((a+b)*c)/d)-(c*b))


Input 2: -ab+c

Read  Operator  Stack operation          Stack content
c        No         push                                  c
+        Yes     pop,pop,push          The second pop fails


Input 3: -abc

Read  Operator  Stack operation          Stack content
c        No         push                                  c
b        No         push                                b,c
a        No         push                              a,b,c
-        Yes     pop,pop,push                       (a-b),c
End of input: ill-formed input expression (stack is too big)

For the sake of simplicity let us restrict our arithmetic expressions as follows:

Part I : Implement the stack

Use the following data type for the stack: 
#define MAXLEN 256

typedef struct {
   char element[MAXLEN][MAXLEN];
   int tos;
} stack;
Write three functions realizing the three stack operations:


Part II: Evaluate a prefix expression

Read an arithmetic expression in prefix notation and use the stack to compute the bracketed infix notation of the input arithmetic expression.

Test input

Show the output of your program on the following inputs: 
+*5+*5+*5+*5+*5UVWXYZ
/++*ac*bd*i-*bc*ad+*cc*dd
+++++abcd---efg**hi/jk
/ab**cde---fghi++++jklmn
+a/1+b/1+c/1+d/1+e/1+f/1+h/1+i/1+j/1+k/1l

Sample output

Input an arithmetic expression in prefix notation :
-/*+abcd*cb
The infix notation for this expression is :
((((a+b)*c)/d)-(c*b))

Input an arithmetic expression in prefix notation :
-ab+c
Error in pop : Stack underflow...

Input an arithmetic expression in prefix notation :
-abc
Error in evaluate: ill-formed expression...


Remark:

The following built-in C functions may prove to be useful for your implementation:

[Course home] [Home]