current symbol operator stack postfix string 1 A A 2 * * A 3 B * A B 4 + + A B * {pop and print the '*' before pushing the '+'} 5 C + A B * C 6 A B * C + The rule used in 1, 3 and 5 is to print an operand when it is read. The rule for line 2 is to push an operator onto the stack if it is empty. The rule for line 4 is if the operator on the top of the stack has higher precedence than the one being read, pop and print the one on top and then push the new operator on. The rule for line 6 is that when the end of the expression has been reached, pop the operators on the stack one at a time and print them. 2. A + B * C becomes A B C * + Here the order of the operators must be reversed. The stack is suitable for this, since operators will be popped off in the reverse order from that in which they were pushed. current symbol operator postfix string 1 A A 2 + + A 3 B + A B 4 * + * A B 5 C + * A B C 6 A B C * + In line 4, the '*' sign is pushed onto the stack because it has higher precedence than the '+' sign which is already there. Then when the are both popped off in lines 6 and 7, their order will be reversed. 3. A * (B + C) becomes A B C + * A subexpression in parentheses must be done before the rest of the expression. current symbol operator stack postfix string 1 A A 2 * * A 3 ( * ( A B 4 B * ( A B
current symbol operator stack postfix string 1 A A 2 * * A 3 B * A B 4 + + A B * {pop and print the '*' before pushing the '+'} 5 C + A B * C 6 A B * C + The rule used in 1, 3 and 5 is to print an operand when it is read. The rule for line 2 is to push an operator onto the stack if it is empty. The rule for line 4 is if the operator on the top of the stack has higher precedence than the one being read, pop and print the one on top and then push the new operator on. The rule for line 6 is that when the end of the expression has been reached, pop the operators on the stack one at a time and print them. 2. A + B * C becomes A B C * + Here the order of the operators must be reversed. The stack is suitable for this, since operators will be popped off in the reverse order from that in which they were pushed. current symbol operator postfix string 1 A A 2 + + A 3 B + A B 4 * + * A B 5 C + * A B C 6 A B C * + In line 4, the '*' sign is pushed onto the stack because it has higher precedence than the '+' sign which is already there. Then when the are both popped off in lines 6 and 7, their order will be reversed. 3. A * (B + C) becomes A B C + * A subexpression in parentheses must be done before the rest of the expression. current symbol operator stack postfix string 1 A A 2 * * A 3 ( * ( A B 4 B * ( A B
DSTC%20lect%20notes.docx