Problem Set 6 (Part 1) — 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. 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: /∗ pop o p e r a n d s from s t a c k ∗/ f o r ( i = 0 ; i < o p o p e r a n d s [ ptoken−>v a l u e . o p c o d e ] ; i f ( ( p v a l u e = pop(& s t a c k v a l u e s ) ) ) { o p e r a n d s [ i ] = pvalue−>v a l u e . operand ; f r e e ( p v a l u e ) ; /∗ done with t o ken ∗/ } else goto e r r o r ; } /∗ p r o c e s s o p e r a n d s a c c o r d i n g t o opcode ∗/ /∗ n o t e o p e r a n d s a r e popped i n r e v e r s e o r d e r ∗/ switch ( ptoken−>v a l u e . o p c o d e ) { case ADD: v a l u e . operand = o p e r a n d s [ 1 ] + o p e r a n d s [ 0 ] ; break ; case SUBTRACT: v a l u e . operand = o p e r a n d s [1] − o p e r a n d s [ 0 ] ; break ; case MULTIPLY: v a l u e . operand = o p e r a n d s [ 1 ] ∗ o p e r a n d s [ 0 ] ; break ; case DIVIDE : v a l u e . operand = o p e r a n d s [ 1 ] / o p e r a n d s [ 0 ] ; break ; case NEGATE: v a l u e . operand = −o p e r a n d s [ 0 ] ; } /∗ push new t o ken with o p e r a t o r r e s u l t t o s t a c k ∗/ push(& s t a c k v a l u e s , new token (OPERAND, v a l u e ) ) ; default : f r e e ( ptoken ) ; /∗ f r e e to ken ∗/ break ; } i ++) { } /∗ r e t u r n v a l u e i s on top o f s t a c k ( s h o u l d be l a s t v a l u e on s t a c k ) ∗/ if ( stack values ) ans = s t a c k v a l u e s −>v a l u e . operand ; cleanup : /∗ f r e e any r e m a i n i n g t o k e n s ∗/ while ( ( ptoken = dequeue ( p q u e u e p o s t f i x ) ) ) f r e e ( ptoken ) ; while ( ( p v a l u e = pop(& s t a c k v a l u e s ) ) ) f r e e ( pvalue ) ; return ans ; error : f p u t s ( " Error evaluating the expression .\ n" , s t d e r r ) ; goto c l e a n u p ; } (b) Now, an infix calculator really is not complete if parentheses are not allowed. So, in this part, update the function infix to postfix() to handle parentheses as we discussed in class. Note: your postfix queue should contain no parentheses tokens. Turn in a printout of your code, along with a printout showing the output from your program for a few test cases utilizing parentheses. Answer: Here’s an implementation: (only function infix to 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 && s t a c k t o p −>type == OPERATOR && ( 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 ; case LPARENS: /∗ pushed t o o p e r a t o r s t a c k ∗/ push(& s t a c k t o p , ptoken ) ; break ; case RPARENS: /∗ pop o p e r a t o r s o f f s t a c k u n t i l l e f t p a r e n t h e s e s r e a c h e d ∗/ f r e e ( ptoken ) ; /∗ p a r e n t h e s e s not i n c l u d e d i n p o s t f i x queue ∗/ while ( ( ptoken = pop(& s t a c k t o p ) ) ) { i f ( ptoken−>type == LPARENS) { f r e e ( ptoken ) ; break ; } enqueue(& q u e u e p o s t f i x , ptoken ) ; } } } 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 ; } Problem 6.2 A useful data structure for storing lots of strings is the “trie.” This tree structure has the special property that a node’s key is a prefix of the keys of its children. For instance, if we associate a node with the string “a,” that node may have a child node with the key “an,” which in turn may have a child node “any.” When many strings share a common prefix, this structure is a very inexpensive way to store them. Another consequence of this storage method is that the trie supports very fast searching – the complexity of finding a string with m characters is O(m). (root) � pointer array of childre � � � "a" "c" � � � � � � � "an" � � � "and" � � � � "ca" � � � � "ant" � � � � "cat" Figure 6.2-1: Trie structure (translations not shown). For each node, its key (e.g. “and”) is not explicitly stored in the node; instead, the key is defined by the node’s position in the tree: the key of its parent node + its index in that parent’s pointer array of children. In this problem, you will utilize a trie structure and to implement a simple one-way Englishto-French dictionary. The trie structure, shown in Figure 6.2-1, consists of nodes, each of which contains a string for storing translations for the word specified at that node and an array of pointers to child nodes. Each node, by virtue of its position in the trie, is associated with a string; in the dictionary context, this string is the word (or part of a word) in the dictionary. The dictionary may contain multiple translations for the same word; in this case, words should be separated by commas. For example: the word like, which has two meanings, could translate as comme, a preposition, or as aimer, a verb. Thus, the translation string should be “comme,aimer.” To get you started, we’ve provided code in prob2.c, which can be downloaded from Stellar. You will need to: • fill in the helper functions new node(), delete node() • complete the function add word(), which adds a word to the trie • complete the function lookup word(), which searches the trie for a word and returns its translation(s) Once your code is working, run a few test cases. Hand in a copy of your code, and a printout of your program running in gdb, with a few example translations to demonstrate functionality. Answer: one possible implementation of the four functions is shown below: /∗ a l l o c a t e new node on t h e heap output : p o i n t e r t o new node ( must be f r e e d ) ∗/ struct s t r i e n o d e ∗ new node ( void ) { /∗ TODO: a l l o c a t e a new node on t h e heap , and i n i t i a l i z e a l l f i e l d s t o d e f a u l t v a l u e s ∗/ struct s t r i e n o d e ∗ pnode = ( struct s t r i e n o d e ∗ ) m a l l o c ( s i z e o f ( struct s t r i e n o d e ) ) ; int i ; pnode−>t r a n s l a t i o n = NULL; f o r ( i = 0 ; i < UCHAR MAX+1; i ++) pnode−>c h i l d r e n [ i ] = NULL; return pnode ; } /∗ d e l e t e node and a l l i t s c h i l d r e n i n p u t : p o i n t e r t o node t o d e l e t e p o s t c o n d i t i o n : node and c h i l d r e n a r e f r e e d ∗/ void d e l e t e n o d e ( struct s t r i e n o d e ∗ pnode ) { /∗ TODO: d e l e t e node and a l l i t s c h i l d r e n Be s u r e t o f r e e non−n u l l t r a n s l a t i o n s ! Hint : u s e r e c u r s i o n ∗/ int i ; i f ( pnode−>t r a n s l a t i o n ) f r e e ( pnode−>t r a n s l a t i o n ) ; f o r ( i = 0 ; i < UCHAR MAX+1; i ++) i f ( pnode−>c h i l d r e n [ i ] ) d e l e t e n o d e ( pnode−>c h i l d r e n [ i ] ) ; f r e e ( pnode ) ; } /∗ add word t o t r i e , with t r a n s l a t i o n i n p u t : word and t r a n s l a t i o n output : non−z e r o i f new node added , z e r o o t h e r w i s e p o s t c o n d i t i o n : word e x i s t s i n t r i e ∗/ i n t add word ( const char ∗ word , char ∗ t r a n s l a t i o n ) { /∗ TODO: add word t o t r i e s t r u c t u r e I f word e x i s t s , append t r a n s l a t i o n t o e x i s t i n g string Be s u r e t o s t o r e a copy o f t r a n s l a t i o n , s i n c e t h e s t r i n g i s r e u s e d by l o a d d i c t i o n a r y ( ) ∗/ struct s t r i e n o d e ∗ pnode = p r o o t ; i n t i , l e n = s t r l e n ( word ) , inew = 0 ; unsigned char j ; f o r ( i = 0 ; i < l e n ; i ++) { j = word [ i ] ; i f ( ( inew = ! pnode−>c h i l d r e n [ j ] ) ) pnode−>c h i l d r e n [ j ] = new node ( ) ; pnode = pnode−>c h i l d r e n [ j ] ; } i f ( pnode−>t r a n s l a t i o n ) { /∗ c o n c a t e n a t e s t r i n g s ∗/ char ∗ o l d t r a n s l a t i o n = pnode−>t r a n s l a t i o n ; int o l d l e n = s t r l e n ( o l d t r a n s l a t i o n ) , newlen = s t r l e n ( t r a n s l a t i o n ) ; pnode−>t r a n s l a t i o n = m a l l o c ( o l d l e n + newlen + 2 ) ; s t r c p y ( pnode−>t r a n s l a t i o n , o l d t r a n s l a t i o n ) ; s t r c p y ( pnode−>t r a n s l a t i o n+o l d l e n , " ," ) ; s t r c p y ( pnode−>t r a n s l a t i o n+o l d l e n +1 , t r a n s l a t i o n ) ; free ( oldtranslation ); } else pnode−>t r a n s l a t i o n = s t r c p y ( m a l l o c ( s t r l e n ( t r a n s l a t i o n )+1) , t r a n s l a t i o n ) ; return inew ; } /∗ s e a r c h t r i e s t r u c t u r e f o r word and r e t u r n t r a n s l a t i o n s i n p u t : word t o s e a r c h output : t r a n s l a t i o n , o r NULL i f not found ∗/ char ∗ lookup word ( const char ∗ word ) { /∗ TODO: s e a r c h t r i e s t r u c t u r e f o r word r e t u r n NULL i f word i s not found ∗/ struct s t r i e n o d e ∗ pnode = p r o o t ; i n t i , l e n = s t r l e n ( word ) ; unsigned char j ; f o r ( i = 0 ; i < l e n ; i ++) { j = word [ i ] ; i f ( ! pnode−>c h i l d r e n [ j ] ) return NULL; pnode = pnode−>c h i l d r e n [ j ] ; } return pnode−>t r a n s l a t i o n ; }