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?

, ,
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.

#### 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