Converting logical formulas from Polish notation to infix notation

Question

I have to write $\land \land \land BA \neg \land BA \to \neg CD$ in infix notation. Usually, my first step consists of sketching the syntax tree. However, since this formula is really messy, my tree didn't look like this:

My intuition isn't always right on these - so is there any systematic way to find the syntax tree?

Another example where I failed was $\to \land E \vee \land \neg A \neg CA\to DC$

Answer 1

For me, it is easier to pretend the whole string is written in Reverse Polish Notation (RPN), i.e. read it right-to-left, and then:

• Whenever you see a terminal symbol ($A, B, C, D$ etc.) push it on the stack
• Whenever you see a unary operation, apply it to the top of the stack and replace the top with it.
• Whenever you see a binary operation, apply it to the pair of two topmost elements of the stack, and replace them with the result.

In particular, with $\land\land\land BA\lnot\land BA\to\lnot CD$, here is what you get on the stack:

$$\begin{array}{|r|r|}\text{Symbol}&\hline\text{Stack}\\\hline D&D\\C&C,D\\\lnot&(\lnot C),D\\\to&((\lnot C)\to D)\\A&A,((\lnot C)\to D)\\B&B,A,((\lnot C)\to D)\\\land&(B\land A),((\lnot C)\to D)\\\lnot&\lnot(B\land A),((\lnot C)\to D)\\A&A,\lnot(B\land A),((\lnot C)\to D)\\B&B,A,\lnot(B\land A),((\lnot C)\to D)\\\land&(B\land A),\lnot(B\land A),((\lnot C)\to D)\\\land&((B\land A)\land(\lnot(B\land A)),((\lnot C)\to D)\\\land&(((B\land A)\land(\lnot(B\land A))\land((\lnot C)\to D))\\\hline\end{array}$$