valiant[188] [~/]> g++ -o hwprog hw.cc valiant[189] [~/]> hwprog Enter tree description : 000000110111000011 In "infix" that would be: ([111]+[000]) valiant[190] [~/]> hwprog Enter tree description : 0000001101110000010110010111 In "infix" that would be: ([111]+(([000]+[101])+[010])) valiant[191] [~/]>Modify the program so that it reads in a string of 0's and 1's representing a compressed file and writes out the decompressed file, like this:
valiant[200] [~/]> g++ -o sol sol.cc valiant[201] [~/]> sol valiant[201] [~/]> sol Enter tree description : 00000011011100001100100100 In "infix" that would be: ([111]+[000]) Decompressed that would be: 111 111 000 111 111 000 111 111 valiant[202] [~/]> sol Enter tree description : 000000110111000001011001011111001001100010001111001 In "infix" that would be: ([111]+(([000]+[101])+[010])) Decompressed that would be: 010 111 111 000 010 111 111 111 000 111 010 010 111 111 valiant[203] [~/]>Turn In a printout of your source code and a screen capture showing your program running on the following input:
000000110000010010010101111110000111011101001011101010001111
Th problem is that we need to represent this "complicated" 2-dimensional binary tree structure as a simple 1-dimensional string of characters. Where have we seen this problem before? Expression trees! Remember, each expression tree can be uniquely represented as a postfix expression, and conversely each postfix expression represents a unique expression tree. This gives us a nice ready-made solution for representing binary trees as 1-dimensional strings of characters.
000000110000010010010101111110000111011101001011101010001111