CS 2C: Adv Data Structures & Algorithms in C++

Preparation:

Step 1: Read Kinds of Algebraic Expressions (section 5.2.1 in the linked text).

Step 2: Read Using Stacks with Algebraic Expressions (section 6.3 in the linked text). Pay close attention to the pseudocode that is provided.

To Do:

Evaluate the following postfix expressions by using the pseudocode given in section 6.3 (the above link, page 206). Create a table that shows the current value of ch and the state of the stack after each step of the algorithm. (One row for each time through the loop.) Use a = 7, b = 3, c = 12, d = -5, e = 1. When you create your table, just write the numbers, not the letters.

1. a. a b c + -
2. b. a b c - d * +
3. c. a b + c - d e * +

Convert the following infix expressions to postfix form by using the pseudocode given in section 6.3 (the above link, page 209). Create a table that shows the values of ch, the stack, and the expression, after each step of the algorithm.

1. d. a - b + c
2. e. a / (b * c)
3. f. (a + b) * c
4. g. a - (b + c)

Here is what your table in parts (a), (b), and (c) would look like if the expression was

ab+c*

value of ch	stack
7	7
3	7,3
+	10
12	10, 12
*	120

For the remaining parts, you can use Figure 6-5 from section 6.3 as a guide to how your table should look.