In this problem, we consider logic expressions with the following operands and o

Question

In this problem, we consider logic expressions with the following operands and operators: Operands: 0 and 1, which represents false and true, respectively. Operators: & (and), | (or), and ! (not). Note that you also have to consider left and right parenthesis. The precedence of the three operators are ! > & > |. (A)Draw the logical expression tree of the expression ! (0&! 1&0|0)&0. Since ! (not) is an unary operator, the only operand should be put to the right child of the operator. Write down its prefix expression. (B)Please write down an algorithm to take a string of logic expression and convert it to an expression tree. (C)Please write down an algorithm to evaluate the outcome of the logical expression using the tree generated by the algorithm in question (b)4(b). (Hint: Postorder traversal)
In this problem, we consider logic expressions with the following operands and operators: Operands: 0 and 1, which represents false and true, respectively. Operators: & (and), | (or), and ! (not). Note that you also have to consider left and right parenthesis. The precedence of the three operators are ! > & > |. (A)Draw the logical expression tree of the expression ! (0&! 1&0|0)&0. Since ! (not) is an unary operator, the only operand should be put to the right child of the operator. Write down its prefix expression. (B)Please write down an algorithm to take a string of logic expression and convert it to an expression tree. (C)Please write down an algorithm to evaluate the outcome of the logical expression using the tree generated by the algorithm in question (b)4(b). (Hint: Postorder traversal)
In this problem, we consider logic expressions with the following operands and operators: Operands: 0 and 1, which represents false and true, respectively. Operators: & (and), | (or), and ! (not). Note that you also have to consider left and right parenthesis. The precedence of the three operators are ! > & > |. (A)Draw the logical expression tree of the expression ! (0&! 1&0|0)&0. Since ! (not) is an unary operator, the only operand should be put to the right child of the operator. Write down its prefix expression. (B)Please write down an algorithm to take a string of logic expression and convert it to an expression tree. (C)Please write down an algorithm to evaluate the outcome of the logical expression using the tree generated by the algorithm in question (b)4(b). (Hint: Postorder traversal)

Explanation / Answer

1 Get the next token. 1.2 If the token is: 1.2.1 A number: push it onto the value stack. 1.2.2 A variable: get its value, and push onto the value stack. 1.2.3 A left parenthesis: push it onto the operator stack. 1.2.4 A right parenthesis: 1 While the thing on top of the operator stack is not a left parenthesis, 1 Pop the operator from the operator stack. 2 Pop the value stack twice, getting two operands. 3 Apply the operator to the operands, in the correct order. 4 Push the result onto the value stack. 2 Pop the left parenthesis from the operator stack, and discard it. 1.2.5 An operator (call it thisOp): 1 While the operator stack is not empty, and the top thing on the operator stack has the same or greater precedence as thisOp, 1 Pop the operator from the operator stack. 2 Pop the value stack twice, getting two operands. 3 Apply the operator to the operands, in the correct order. 4 Push the result onto the value stack. 2 Push thisOp onto the operator stack. 2. While the operator stack is not empty, 1 Pop the operator from the operator stack. 2 Pop the value stack twice, getting two operands. 3 Apply the operator to the operands, in the correct order. 4 Push the result onto the value stack. 3. At this point the operator stack should be empty, and the value stack should have only one value in it, which is the final result.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.