Programming MIT Problem Set 6 - Solutions

Massachusetts Institute of Technology
Department of Electrical Engineering and Computer Science

6.087: Practical Programming in C

IAP 2010

Problem Set 6 – Solutions
Part 1: Pointers to pointers. Multidimensional arrays. Stacks and queues.

Out: Wednesday, January 20, 2010. Due: Friday, January 22, 2010.

This is Part 1 of a two-part assignment. Part 2 will be released Thursday.

Problem 6.1
In this problem, we will implement a simple “four-function” calculator using stacks and queues.
This calculator takes as input a space-delimited infix expression (e.g. 3 + 4 * 7), which you
will convert to postfix notation and evaluate. There are four (binary) operators your calculator
must handle: addition (+), subtraction (-), multiplication (*), and division (/). In addition, your
calculator must handle the unary negation operator (also -). The usual order of operations is in
effect:

• the unary negation operator - has higher precedence than the binary operators, and is eval­
uated right-to-left (right-associative)

• * and / have higher precedence than + and ­

• all binary operators are evaluated left-to-right (left-associative)

To start, we will not consider parentheses in our expressions. The code is started for you in prob1.c,
which is available for download from Stellar. Read over the file, paying special attention to the
data structures used for tokens, the stack, and queue, as well as the functions you will complete.

(a) We have provided code to translate the string to a queue of tokens, arranged in infix (natural)
order. You must:

– fill in the infix to postfix() function to construct a queue of tokens arranged in
postfix order (the infix queue should be empty when you’re done)
– complete the evaluate postfix() function to evaluate the expression stored in the
postfix queue and return the answer

You may assume the input is a valid infix expression, but it is good practice to make your
code robust by handling possible errors (e.g. not enough tokens) . Turn in a printout of your
code, along with a printout showing the output from your program for a few test cases (infix
expressions of your choosing) to demonstrate it works properly.




1

, Answer: Here’s one possible implementation: (only functions infix to postfix() and
evaluate postfix() shown)
/∗ c r e a t e s a queue o f t o k e n s i n p o s t f i x o r d e r from a queue o f t o k e n s i n i n f i x o r d e r ∗/
/∗ p o s t c o n d i t i o n : r e t u r n e d queue c o n t a i n s a l l t h e t o k e n s , and p q u e u e i n f i x s h o u l d be
empty ∗/
struct t o k e n q u e u e i n f i x t o p o s t f i x ( struct t o k e n q u e u e ∗ p q u e u e i n f i x ) {
/∗ TODO: c o n s t r u c t p o s t f i x −o r d e r e d queue from i n f i x −o r d e r e d queue ;
a l l t o k e n s from i n f i x queue s h o u l d be added t o p o s t f i x queue o r f r e e d ∗/
p e x p r t o k e n s t a c k t o p = NULL, ptoken ;
struct t o k e n q u e u e q u e u e p o s t f i x ;

q u e u e p o s t f i x . f r o n t = q u e u e p o s t f i x . back = NULL;
f o r ( ptoken = dequeue ( p q u e u e i n f i x ) ; ptoken ; ptoken = dequeue ( p q u e u e i n f i x ) ) {
switch ( ptoken−>type ) {
case OPERAND:
/∗ o p e r a n d s added d i r e c t l y t o p o s t f i x queue ∗/
enqueue(& q u e u e p o s t f i x , ptoken ) ;
break ;
case OPERATOR:
/∗ o p e r a t o r added t o s t a c k , a f t e r o p e r a t o r s o f h i g h e r
p r e c e d e n c e a r e moved t o queue ∗/
while ( s t a c k t o p &&
( o p p r e c e d e n c e s [ s t a c k t o p −>v a l u e . o p c o d e ] >
o p p r e c e d e n c e s [ ptoken−>v a l u e . o p c o d e ] | |
( o p p r e c e d e n c e s [ s t a c k t o p −>v a l u e . o p c o d e ] ==
o p p r e c e d e n c e s [ ptoken−>v a l u e . o p c o d e ] &&
o p a s s o c i a t i v i t y [ o p p r e c e d e n c e s [ ptoken−>v a l u e . o p c o d e ] ] == LEFT ) ) )
enqueue(& q u e u e p o s t f i x , pop(& s t a c k t o p ) ) ;
push(& s t a c k t o p , ptoken ) ;
break ;
default : /∗ o t h e r t o k e n s i g n o r e d ∗/
f r e e ( ptoken ) ;
break ;
}
}
while ( s t a c k t o p ) /∗ pop r e m a i n i n g o p e r a t o r s o f f s t a c k ∗/
enqueue(& q u e u e p o s t f i x , pop(& s t a c k t o p ) ) ;
return q u e u e p o s t f i x ;
}

/∗ e v a l u t e s t h e p o s t f i x e x p r e s s i o n s t o r e d i n t h e queue ∗/
/∗ p o s t c o n d i t i o n : r e t u r n e d v a l u e i s f i n a l answer , and p q u e u e p o s t f i x s h o u l d be empty ∗/
double e v a l u a t e p o s t f i x ( struct t o k e n q u e u e ∗ p q u e u e p o s t f i x ) {
/∗ TODO: p r o c e s s p o s t f i x −o r d e r e d queue and r e t u r n f i n a l answer ;
a l l t o k e n s from p o s t f i x −o r d e r e d queue i s f r e e d ∗/
double ans = 0 . ;
p e x p r t o k e n s t a c k v a l u e s = NULL, ptoken , p v a l u e ;
double o p e r a n d s [ 2 ] ; /∗ max two o p e r a n d s ∗/
union t o k e n v a l u e v a l u e ;
int i ;

while ( ( ptoken = dequeue ( p q u e u e p o s t f i x ) ) ) {
switch ( ptoken−>type ) {
case OPERAND:
/∗ o p e r a n d s a lways pushed t o s t a c k ∗/
push(& s t a c k v a l u e s , ptoken ) ;
break ;
case OPERATOR:


2