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

LAB TEST 3

For students with even PC numbers


[Evaluation of arithmetic expressions in postfix 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 postfix notation one writes the operands first (the first and the second in that order) and then the operator. Some examples are given below: 

infix                       postfix
a                         a
a+b                       ab+
(a+b)*c                   ab+c*
((a+b)*c)/d               ab+c*d/
((a+b)*c)/d-(e*f)         ab+c*d/ef*-
(((a-5)*c+3)/2)-(a-8*c)   a5-c*3+2/a8c*--
Irrespective of the precedence of the operators the postfix 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 postfix notations for a-(8*c) and (a-8)*c are different, namely a8c*- and a8-c*.

Given a postfix 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 character-by-character (from beginning to end). 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 postfix 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: ab+c*d/cb*-

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


Input 2: a+bc-

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


Input 3: abc-

Read  Operator  Stack operation          Stack content
a        No         push                                  a
b        No         push                                b,a
c        No         push                              c,b,a
-        Yes     pop,pop,push                       (b-c),a
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 postfix expression

Read an arithmetic expression in postfix 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: 
77777a*b+*c+*d+*e+*f+
AC*BD*+IBC*AD*-*+CC*DD*+/
abcde++++fghi---jkl**mn/
ab/cd**efg---hijk+++++
a1b1c1d1e1f1g1h1j1k1l/+/+/+/+/+/+/+/+/+/+

Sample output

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

Input an arithmetic expression in postfix notation :
a+bc-
Error in pop : Stack underflow...

Input an arithmetic expression in postfix 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]