Recursive definition of sets

Question

I'm having trouble understanding the following problem:

I have three sets, the first one contains $$S=\{a,b,c\}$$

The second contains operators (plus, times, bullet) $$O=\{+, \times, \bullet\}$$

The third one, E is a set of "well written expressions" defined by the following two rules:

$$(1) \text{ if } x \in S \text{, then } x \in E$$ $$(2) \text{ if } X,Y \in E \text{ and } * \in O \text{ then } *XY \in E$$

Now I have multiple expressions and I must verify if they are "correct". The issue is when I try to interpret the rules. The first one stipulates that for any letter in S it exists in E. the second says that for an expression in E and a symbol in O the combination also exists in E? How can I try to mathematically prove that a given expression is in E ex: $$+ a\times bc$$ Thanks!

Answer 1

For this question, the "well-written expressions" are in Polish notation. Each operator takes $2$ arguments, so we can parse an expression going from left to right as follows:

• Upon encountering any symbol, immediately push it onto the stack.
• If, after such a push, the top of the stack reads $o,e_1,e_2$ with $o\in O$, $e_1,e_2\in E$ and $e_2$ the top element, pop those three elements and push $(o\ e_1 e_2)\in E$. Repeat until this is no longer possible before continuing.

If exactly one element remains after these actions, the expression is in $E$.