Question

For each of these strings, determine whether it is generated by the grammar given for postfix notation. If it is, find the steps used to generate the string.

\(\begin{array}{l}{\bf{a) abc* + }}\\{\bf{b) xy + + }}\\{\bf{c) xy - z*}}\\{\bf{d) wxyz - */ }}\\{\bf{e) ade - *}}\end{array}\)

Short answer

a) The \(abc* + \) expression is obtained.

b) The \(xy + + \) expression is not obtained.

c) The \(xy - z*\) expression is obtained.

d) The \(wxyz - */\) expression is obtained.

e) The \(ade - *\) expression is obtained.

Step-by-step solution

Definition of postfix notation

Use ordered rooted trees to represent complex expressions like mathematical expressions, set combinations, and compound propositions.

Consider how an arithmetic phrase with the operators + (addition), - (subtraction), + (multiplication), / (division), and is represented (exponentiation).

Create the steps to generate the string. 

(a)

The following can be deduced from the string\(abc* + \):

\(\begin{array}{*{20}{l}}\begin{array}{c}\left\langle {\exp ression} \right\rangle \mathop = \limits^* > \left\langle {term} \right\rangle \left\langle {term} \right\rangle \left\langle {addOperator} \right\rangle {\bf{ }}\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {factor} \right\rangle \left\langle {factor} \right\rangle \left\langle {mulOperator} \right\rangle \left\langle {addOperator} \right\rangle \end{array}\\{\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {identifier} \right\rangle \left\langle {identifier} \right\rangle \left\langle {identifier} \right\rangle \left\langle {mulOperator} \right\rangle \left\langle {addOperator} \right\rangle }\\{\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > abc* + }\end{array}\)

To generate the string first we take the expression, and then it could be expanded using the rule;

\(\left\langle {\exp ression} \right\rangle :: = \left\langle {term} \right\rangle |\left\langle {term} \right\rangle \left\langle {term} \right\rangle \left\langle {addOperator} \right\rangle \)

Then using the rule,

\(\left\langle {term} \right\rangle :: = \left\langle {factor} \right\rangle |\left\langle {factor} \right\rangle \left\langle {factor} \right\rangle \left\langle {mulOperator} \right\rangle \)it is expanded again.

Now rule.

\(\left\langle {factor} \right\rangle :: = \left\langle {identifier} \right\rangle \left\langle {\exp ression} \right\rangle \) is applied to generate the next line.

Hence, the given expression is obtained.

 Create the steps to generate the string.

(b)

This \(xy + + \)expression is not generated as there are two s followed by two

\(\left\langle {addOperator} \right\rangle S\)

The following can be deduced from the string \(xy + + \)

\(\begin{array}{*{20}{l}}\begin{array}{c}\left\langle {\exp ression} \right\rangle \\\mathop = \limits^* > \left\langle {term} \right\rangle \left\langle {term} \right\rangle \left\langle {addOperator} \right\rangle \\\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {term} \right\rangle \left\langle {addOperator} \right\rangle \end{array}\\{\mathop = \limits^* > \left\langle {identifier} \right\rangle \left\langle {term} \right\rangle \left\langle {addOperator} \right\rangle }\\\begin{array}{l}\mathop = \limits^* > x\left\langle {term} \right\rangle \left\langle {addOperator} \right\rangle \\ = > x\left\langle {factor} \right\rangle \\ = > x\left\langle {\exp ression} \right\rangle \\ = > x\left\langle {term} \right\rangle \left\langle {term} \right\rangle \left\langle {addOperator} \right\rangle {\bf{ }}\end{array}\end{array}\)

Thus, the given expression is not obtained.

 Create the steps to generate the string.

(c)

The given string \(xy - z*\)can be derived as:

\(\begin{array}{*{20}{l}}\begin{array}{c}\left\langle {\exp ression} \right\rangle \mathop = \limits^* > \left\langle {term} \right\rangle {\bf{ }}\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {factor} \right\rangle \left\langle {mulOperator} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {\exp ression} \right\rangle \left\langle {factor} \right\rangle \left\langle {mulOperator} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {term} \right\rangle \left\langle {term} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {factor} \right\rangle \left\langle {mulOperator} \right\rangle \end{array}\\{\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {identifier} \right\rangle \left\langle {identifier} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {identifier} \right\rangle \left\langle {mulOperator} \right\rangle }\\{\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > xy - z*}\end{array}\)

Accordingly, the given expression is obtained.

 Create the steps to generate the string.

(d)

The given string \(wxyz - */\)can be derived as:

\(\begin{array}{c}\left\langle {\exp ression} \right\rangle \mathop = \limits^* > \left\langle {term} \right\rangle \\\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {factor} \right\rangle \left\langle {mulOperator} \right\rangle \\\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {\exp ression} \right\rangle \left\langle {mulOperator} \right\rangle \\\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {factor} \right\rangle \left\langle {factor} \right\rangle \left\langle {mulOperator} \right\rangle \left\langle {mulOperator} \right\rangle \end{array}\)

\(\begin{array}{c}\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {factor} \right\rangle \left\langle {\exp ression} \right\rangle \left\langle {mulOperator} \right\rangle \left\langle {mulOperator} \right\rangle \\\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {factor} \right\rangle \left\langle {term} \right\rangle \left\langle {term} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {mulOperator} \right\rangle \left\langle {mulOperator} \right\rangle \\\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {factor} \right\rangle \left\langle {factor} \right\rangle \left\langle {factor} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {mulOperator} \right\rangle \left\langle {mulOperator} \right\rangle \\\mathop = \limits^* > \left\langle {identifier} \right\rangle \left\langle {identifier} \right\rangle \left\langle {identifier} \right\rangle \left\langle {identifier} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {mulOperator} \right\rangle \left\langle {mulOperator} \right\rangle \\\mathop = \limits^* > wxyz - */\end{array}\)

So, the given expression is obtained.

Create the steps to generate the string.

(e)

The given string \(ade - *\)can be derived as:

\(\begin{array}{*{20}{l}}\begin{array}{c}\left\langle {\exp ression} \right\rangle \mathop = \limits^* > \left\langle {term} \right\rangle {\bf{ }}\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {factor} \right\rangle \left\langle {mulOperator} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {\exp ression} \right\rangle \left\langle {mulOperator} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {term} \right\rangle \left\langle {term} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {mulOperator} \right\rangle \\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {factor} \right\rangle \left\langle {factor} \right\rangle \left\langle {factor} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {mulOperator} \right\rangle \end{array}\\{\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > \left\langle {identifier} \right\rangle \left\langle {identifier} \right\rangle \left\langle {identifier} \right\rangle \left\langle {addOperator} \right\rangle \left\langle {mulOperator} \right\rangle }\\{\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathop = \limits^* > ade - *}\end{array}\)

Therefore, the given expression is obtained.