In: Computer Science
C++ Use BinaryNodeTree to solve the following questions in a program:
1) What is the value of the prefix expression +−∗ 235/↑ 2 3 4?
2) What is the postfix form of the expression ((x + y) ↑ 2) + ((x − 4)/3)?
3) What is the value of the postfix expression723 ∗ − 4 ↑ 9 3/+?
QUE : 1) What is the value of the prefix expression +−∗ 235/↑ 2 3 4?
Symbol | Opnd 1 | Opnd 2 | Value | Opndstack |
4 | 4 | |||
3 | 4,3 | |||
2 | 4,3,2 | |||
↑ | 2 | 3 | 8 | 4 |
4,8 | ||||
/ | 8 | 4 | 2 | |
2 | ||||
5 | 2,5 | |||
3 | 2,5,3 | |||
2 | 2,5,3,2 | |||
* | 2 | 3 | 6 | 2,5 |
2,5,6 | ||||
- | 6 | 5 | 1 | 2 |
2,1 | ||||
+ | 1 | 2 | 3 | |
VALUE = | 3 | |||
VALUE For given prefix expression +−∗ 235/↑ 2 3 4 is 3.
_______________________________________________________________________
QUE: 2) What is the postfix form of the expression ((x + y) ↑ 2) + ((x − 4)/3)?
ANS:
Input String | Output Stack | Operator Stack |
---|---|---|
((x + y) ↑ 2) + ((x − 4)/3) | ( | |
((x + y) ↑ 2) + ((x − 4)/3) | (( | |
((x + y) ↑ 2) + ((x − 4)/3) | x | (( |
((x + y) ↑ 2) + ((x − 4)/3) | x | (( |
((x + y) ↑ 2) + ((x − 4)/3) | x | ((+ |
((x + y) ↑ 2) + ((x − 4)/3) | x | ((+ |
((x + y) ↑ 2) + ((x − 4)/3) | x y | ((+ |
((x + y) ↑ 2) + ((x − 4)/3) | x y+ | ( |
((x + y) ↑ 2) + ((x − 4)/3) | x y+ | ( |
((x + y) ↑ 2) + ((x − 4)/3) | x y+ ↑ | ( |
((x + y) ↑ 2) + ((x − 4)/3) | x y+ ↑ | ( |
((x + y) ↑ 2) + ((x − 4)/3) | x y+ ↑ 2 | ( |
((x + y) ↑ 2) + ((x − 4)/3) | x y+ ↑ 2 | |
((x + y) ↑ 2) + ((x − 4)/3) | x y+ ↑ 2 | |
((x + y) ↑ 2) + ((x − 4)/3) | x y+ ↑ 2 | + |
((x + y) ↑ 2) + ((x − 4)/3) | x y+ ↑ 2 | + |
((x + y) ↑ 2) + ((x − 4)/3) | x y+ ↑ 2 | +( |
((x + y) ↑ 2) + ((x − 4)/3) | x y+ ↑ 2 | +(( |
((x + y) ↑ 2) + ((x − 4)/3) | x y+ ↑ 2 x | +(( |
((x + y) ↑ 2) + ((x − 4)/3) | x y+ ↑ 2 x | +(( |
((x + y) ↑ 2) + ((x − 4)/3) | x y+ ↑ 2 x − | +(( |
((x + y) ↑ 2) + ((x − 4)/3) | x y+ ↑ 2 x − | +(( |
((x + y) ↑ 2) + ((x − 4)/3) | x y+ ↑ 2 x − 4 | +(( |
((x + y) ↑ 2) + ((x − 4)/3) | x y+ ↑ 2 x − 4 | +( |
((x + y) ↑ 2) + ((x − 4)/3) | x y+ ↑ 2 x − 4 | +(/ |
((x + y) ↑ 2) + ((x − 4)/3) | x y+ ↑ 2 x − 43 | +(/ |
((x + y) ↑ 2) + ((x − 4)/3) | x y+ ↑ 2 x − 43/ | + |
((x + y) ↑ 2) + ((x − 4)/3) | x y+ ↑ 2 x − 43/+ |
Que : 3) What is the value of the postfix expression723 ∗ − 4 ↑ 9 3/+?
ANS :
723 ∗ − 4 ↑ 9 3/+
The first character scanned is "723", which is an operand, so push it to the stack.
723 |
|
|
Stack | Expression |
___________________________________________________________________________________________
723 ∗ − 4 ↑ 9 3/+
The next character scanned is "∗", which is an operator, so pop its two operands from the stack. Pop 723 from the stack for the right operand and then pop undefined from the stack to make the left operand.
undefined ∗ 723 = 0 |
||
Stack | Expression |
Next, push the result of undefined ∗ 723 (0) to the stack.
0 |
|
|
Stack | Expression |
__________________________________________________________________________________________
723 ∗ − 4 ↑ 9 3/+
The next character scanned is "−", which is an operator, so pop its two operands from the stack. Pop 0 from the stack for the right operand and then pop undefined from the stack to make the left operand.
undefined − 0 = 0 |
||
Stack | Expression |
Next, push the result of undefined − 0 (0) to the stack.
0 |
|
|
Stack | Expression |
_______________________________________________________________________________________
723 ∗ − 4 ↑ 9 3/+
The next character scanned is "4", which is an operand, so push it to the stack.
4 0 |
|
|
Stack | Expression |
_______________________________________________________________________________________
723 ∗ − 4 ↑ 9 3/+
The next character scanned is "↑", which is an operator, so pop its two operands from the stack. Pop 4 from the stack for the right operand and then pop 0 from the stack to make the left operand.
0 ↑ 4 = 0 |
||
Stack | Expression |
Next, push the result of 0 ↑ 4 (0) to the stack.
0 |
|
|
Stack | Expression |
_________________________________________________________________________________________
723 ∗ − 4 ↑ 9 3/+
The next character scanned is "9", which is an operand, so push it to the stack.
9 0 |
|
|
Stack | Expression |
_________________________________________________________________________________________
723 ∗ − 4 ↑ 9 3/+
The next character scanned is "3/+", which is an operator, so pop its two operands from the stack. Pop 9 from the stack for the right operand and then pop 0 from the stack to make the left operand.
0 3/+ 9 = 0 |
||
Stack | Expression |
Next, push the result of 0 3/+ 9 (0) to the stack.
0 |
|
|
Stack | Expression |
Since we are done scanning characters, the remaining element in the stack (0) becomes the result of the postfix evaluation.
Postfix notation: 723 ∗ − 4 ↑ 9 3/+
Result: 0