either a prefix or a postfix notation logical expression, and a
dictionary of variable names and their values returns the
valuerepresented by the expression corresponding to the given
values of the variables. (Binary Tree)
Note: Must write this in C++ language.
- Write A C Function That Receives A Constant String Which Is Either A Prefix Or A Postfix Notation Logical Expression 1 (21.96 KiB) Viewed 99 times
- Write A C Function That Receives A Constant String Which Is Either A Prefix Or A Postfix Notation Logical Expression 2 (14.84 KiB) Viewed 99 times
- Write A C Function That Receives A Constant String Which Is Either A Prefix Or A Postfix Notation Logical Expression 3 (39.22 KiB) Viewed 99 times
- Write A C Function That Receives A Constant String Which Is Either A Prefix Or A Postfix Notation Logical Expression 4 (32.36 KiB) Viewed 99 times
"p&!q>r|s" (the input should be the number instead of
p,q,r,s. For example p=1, q=0, r=1 and s=0. So input you should
write in the program is the prefix or postfix of "1&!0>1|0"
to return value 1)
Output: return the integer value
Thanks for helping and solving. Please don't spam any incorrect
answers.
In this assignment, we will modify the above algorithms to adapt to logical expressions. For example, the parse tree representing the infix-notation expression “p^q=rVs” is given in Fig. 2. By means of the algorithm PostorderTree Traversal, the postfix-notation of the expression is "pq - Ars V". With this postfix notation and for specific values of propositions p, q, r, and s, for example, p=1,q=0, r= 1, and s = 0, we aim that the modified algorithm returns 1.
A р 9 Fig. 2: The parse tree representing the infix-notation expression “p-q-rVs"
Logical operator Meaning (use &) Conjunction V(use D Disjunction Examples (1 = true, 0= Operand and false) output data type ΙΛΙ=Ι, ΙΛΟ=0, ΟΛΟ=0 (Boolean, Boolean, Boolean) 1V1=1, 1V0=1,000=0 (Boolean, Boolean, Boolean) 11=1,1-0=0,0–0=1 (Boolean, Boolean, Boolean) -1=0.0=1, 1=1 (Boolean, Boolean, Boolean) 101=0,100=1,000=0 (Boolean, Boolean, Boolean) (use >) Implication -(use!) Negation (use +) Exclusive Or Tab. 9: Operators and data types of operands used in inputs of logical expressions
Type Consecutive operators Examples Exceptions PAM, PVV, PV, p-Aq raise P, p.4,p——— undefined error pΛqVr, pVqAr raise PA-4, pq->r, p-> multi-output error (pA(q)Vr, (pVq))(Ar raise syntax (PAO)Vr, ((pA(qVr)) Precedence order Parenthesis error Blank p 4, p1-9 error r raise syntax P V4-r, pq (name of a proposition) Tab. 10: Ambiguous and illegal input cases of logical expressions
I. Introduction: People usually evaluate a (arithmetic) expression by using its infix notation, where every operator lies in between two operands in the expression. For example, the expression "24/(6+2)-3" is evaluated to 0 because the sum of 6 and 2 in the parentheses equals to 8, the division “24/8” evenly equals to 3, and 3 is then subtracted from it, which results in 0. However, it's not an effective way for a computer to evaluate such an expression. The computers use the prefix or postfix notations instead. 1) Prefix, infix, and postfix notations: Let E be the expression “24/(6+2)-3". We study its prefix and postfix notations. By means of graph theory, E can be represented by the following graph.
24 Fig. 1: Graph representation of the expression “24/(6+2)-3 Indeed, we can make E clearer by adding some extra parentheses to it. The expression E then becomes "((24/(6+2))-3)". Now we can represent the innermost sum as a binary tree with 3 nodes only, where the root of the tree is the addition operator and the two leaves are the numbers 6 and 2. This tree doesn't have internal nodes unless we consider the root as an internal node. By thinking that way, we can imagine that the division 24/(6+2)" can be also represented by a binary tree, where the root is the division operator, the left node of the root is the number 24 and the right-hand-side of the root is, however, no longer a single node with no child but a subtree representing the sum "6+2". We proceed and end up with a complete tree as in Fig. 1. With this representation, we can define the prefix and postfix notations for the expression E by performing the Pre-order and Post-order Tree Traversal algorithms respectively on the tree starting from the root. Here we consider non-recursive algorithms. Algorithm PreoderTree Traversal Input: a binary tree Output: an ordered list of the nodes of the tree Step 1: Create an empty list and an empty stack.
Step 2: Push the root of the tree into the stack. Step 3: Repeat the following steps until the stack is empty. Step 3a: Pop one node off the stack and add it to the list. Step 3b: Push the right-hand-side child of the node into the stack and then the left-hand-side one if they exist. Tab. 1: Pre-order Tree Traversal Algorithm / 3 W+ 24 2 33 WN 2 3 Tab. 2: Stack behavior when we apply the algorithm Preorder Tree Traversal to the graph in Fig. 1 Algorithm PostoderTree Traversal Input: a binary tree Output: an ordered list of the nodes of the tree Step 1: Create an empty list and an empty stack. Step 2: Push the root of the tree into the stack. Step 3: Repeat the following steps until the stack is empty. Step 3a: Pop one node off the stack and add it to the list if it doesn't have children. Otherwise, go to Step 3b. Step 3b: Push the right-hand-side child of the node into the stack and then the left-hand-side one. Go to Step 3. Tab. 3: Post-order Tree Traversal Algorithm 6 2 + + 24 + / 3 / 3 / 3 1 3 3 3 3
Tab, 4: Stack behavior when we apply the algorithm Postorder Tree Traversal to the graph in Fig. For example, the behavior of the stack when we apply the algorithm Preorder Tree Traversal and Postorder Tree Traversal to the graph in Fig. I are given in Tab. I, Tab. 3, and the resulting lists are "-/24 +62 3" and "24 6 2 + 3" respectively, 2) Evaluating arithmetic expressions: We discuss how a computer evaluates prefix/postfix-notation arithmetic expressions. Let's consider the expression “24 6 2 +/3 -". The idea is to scan through the expression from left to right (from right to left if it's a prefix-notation expression). On the other hand, we use a stack to store only the operands. Algorithm PostfixEvaluation Input: a postfix-notation arithmetic expression Output: the value represented by the expression Step 1: Create an empty stack. Step 2: Scan through the expression from left to right and repeat the following steps until the whole expression is scanned through completely. Step 2a: If it is an operand, push it into the stack. Otherwise, go to Step 2b. Step 2b: Pop 2 items off the stack, perform the operation, and add the resulting value to the stack Step 3: Return the last item added to the stack. Tab, 5: Postfix Evaluation Algorithm 6 24 2 6 6 24 24 24 8 24 24 3 3 3 3 24 Tab. 6: Stack behavior when we apply the algorithm PostfixEvaluation to evaluate the expression "246 2/3 -".
Firstly, we push the 3 consecutive numbers 24, 6, 2 into the stack. The plus sign is then encountered, we pop 2 and 6 off the stack, perform the addition “6+2" to obtain 8, and add 8 to the stack. After those steps, the division operator is encountered. Thus, we pop 8 and 24 off the stack and calculate the division “24/8”, which equals to 3. The number 3 is then pushed into the stack and is taken off the stack together with the other number 3 because the minus sign is encountered. Finally, we calculate “3-3" and push 0 into the stack. This is also the last operation that we do. Therefore, the value represented by the expression is 0. For expressions that haven't transformed into prefix or postfix-notation yet. We need to build their representing trees and perform the pre-order or post-order tree traversal algorithms before we apply the algorithm to evaluate the expression. If it is the case, the algorithm building the trees must take care of the precedence order. For example, the tree representing the expression "24/(6+2)-3”, which is evaluated to 0, is different from the tree representing the expression "24/6+(2-3)", which is evaluated to 3. Moreover, we also need to be very careful about the negative numbers in the expressions. For example, the expression "6/(-3)+2" has the postfix-notation "63 - / 2 +", which may be considered as a critical case to the algorithm Postfix Evaluation to evaluate the expression.