World's most popular travel blog for travel bloggers.

Is the number of operators always one less than the number of values in an arithmetic Reverse Polish Notation expression with only binary operators?

, , No Comments
Problem Detail: 

Is the number of operators always one less than the number of values in an arithmetic Reverse Polish Notation expression with only binary operators?

This question seems very trivial, but I don't know if the statement is necessarily true for all N > 1 where N is the number of values. It seems intuitively true because any expression with more than one binary operator can be expressed as a combination of two different expressions through induction, but I'm not very confident.

Asked By : Sky

Answered By : Yuval Filmus

RPN expressions have stack semantics: a value pushes a number onto the stack, whereas a binary operator pops two values and pushes one back, for a net loss of one element. At the start of an expression the stack is empty, and at the end there is exactly one value – the result.

Now let $V$ be the number of values in the expression, and $B$ be the number of binary operators. Then at the end of the expression, the stack contains $V-B$ values. Since there should be exactly one value remaining, we conclude that $V-B = 1$, or $B = V-1$.


Another way to see this is using structural induction. As you mention, every expression is either a value or is obtained from two expressions combined using a binary operator. Let's prove by induction on the number of values and operators appearing in the expression that $V = B+1$ (in the terminology of the preceding section).

When the expression consists of just a value, $B=0$ and $V=1$, so $V = B+1$. When the expression consists of a binary operator together with two other expressions $E_1,E_2$, we have $V = V(E_1)+V(E_2)$ and $B = B(E_1)+B(E_2)+1$ (I hope the notation is clear). By induction, $V(E_1) = B(E_1)+1$ and $V(E_2) = B(E_2)+1$, so $$ V = V(E_1) + V(E_2) = B(E_1) + 1 + B(E_2) + 1 = B + 1. $$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/53978

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback