Cheap and Secure Web Hosting Provider : See Now

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