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.

  • $\begingroup$ I don't need a proof. This is the wrong sentiment when trying to learn computer science. We're not here to help you with your homework – we're here to help you understand the material, so that you can do your homework yourself next time. $\endgroup$ – Yuval Filmus Mar 4 '16 at 10:53
  • $\begingroup$ I'm really sorry; I was mostly trying to ask if this statement is even true in the first place. I didn't really want to ask for a proof because that will waste people's time since it's probably trivial to everyone here. $\endgroup$ – Sky Mar 4 '16 at 13:18

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


A simple inductive argument will work here. Expressions in RPN can be defined recursively by using the grammar:

E: operand
E: E E operator

Where E is an expression, operand is a number and operator is a binary operator.

The base case is when the expression is just a number. In this case the number of operators is clearly one less than the number of operands.

Let E be an expression of length n > 1 and assume that the statement is true for expressions of length < n (n here is the number of operands). The expression is of the form E1 E2 operator. The first two expressions have smaller lengths and so we have:

o1 = n1 - 1.
o2 = n2 - 1.
o = o1 + o2 + 1 = n1 + n2 - 2 + 1 = n - 1 (we add 1 for the `operator` in `E1 E2 operator`).

o stands for number of operators. n stands for number of operands.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.