55. Reverse Polish notation

Question 1

convert the following reverse polish notation expression to its equivalent infix expression:
4 6 +

Answer 1

4 + 6

Question 2

convert the following reverse polish notation expression to its equivalent infix expression:
8 2 -

Answer 2

8 -2

Question 3

convert the following reverse polish notation expression to its equivalent infix expression:
4 9 + 6 x

Answer 3

(4 + 9) x 6

Question 4

convert the following reverse polish notation expression to its equivalent infix expression:
10 4 7 + x

Answer 4

10 x (4 + 7)

Question 5

convert the following reverse polish notation expression to its equivalent infix expression:
3 9 + 4 2 - x

Answer 5

(3 + 9) x (4 - 2)

Question 6

convert the following infix notation expression to its equivalent reverse polish notation expression:
4 + 3

Answer 6

4 3 +

Question 7

convert the following infix notation expression to its equivalent reverse polish notation expression:
56 - 40

Answer 7

56 40 -

Question 8

convert the following infix notation expression to its equivalent reverse polish notation expression:
5 x (5 - 3)

Answer 8

5 5 3 - x

Question 9

convert the following infix notation expression to its equivalent reverse polish notation expression:
(6 / 3) + (6 + 2)

Answer 9

6 3 / 6 2 + +

Question 10

convert the following infix notation expression to its equivalent reverse polish notation expression:
(18 - 8) x (30 + 20)

Answer 10

18 8 - 30 20 + x

Question 11

why do we use reverse polish notation?

Answer 11

it eliminates the need for brackets in sub-expressions
it produces expressions in a form suitable for evaluation using a stack
it is used in interpreters based on stack; for example, postscript and bytecode
operands and operators need to be in correct sequence for computer to execute

Question 12

what do we refer to regular way we write arithmetic expressions as?

Answer 12

infix notation

Question 13

another name for reverse polish notation?

Answer 13

postfix notation

Question 14

what is the first step in translating from infix to reverse polish notation?

Answer 14

define the order of precedence of operators

e.g. = ( + - ) * / ^ ~

Question 15

describe the evaluation of reverse polish notation using a stack

Answer 15

once a compiler has translated and arithmetic expression into RPN, each symbol in the expression may be held in a string or array
the expression may then be evaluated using a stack scanning the elements of the string (or array) from left to right
- if the next token is an operand, place it on the stack
- if the next token is an operator, remove the required number of the operands from the stack, perform the operation, and put the result on the stack

Question 16

when using a in-order traversal of a binary expression tree to represent expressions, what corresponding format will the algebraic expression be in?

Answer 16

Infix

Question 17

when using a post-order traversal of a binary expression tree to represent expressions, what corresponding format will the algebraic expression be in?

Answer 17

Postfix