Solving a Postfix Expression: ABCD+*/E- Tree

In summary: Then, once you have that, you can work backwards to construct the tree and then the postfix expression.In summary, the conversation is discussing how to convert a postfix expression into a binary tree by thinking of letters as instructions to put on a stack and operators as pulling items off the stack and performing operations. The conversation also suggests working backwards from an equivalent infix expression to construct the tree and postfix expression.
  • #1
Bucs44
57
0

Homework Statement


I am having a hard time figuring out this postfix expression and turning it into a binary tree: ABCD+*/E-



The Attempt at a Solution



what's confusing me is the left side of the tree - the ABCD - I know the right side of the tree would look like this: - is the root and * / E

Any help would be greatly appreciated
 
Physics news on Phys.org
  • #2
When you see a letter, think of it as an instruction to put it on a stack. When you see an operator, think of pulling the last two things off the stack and pushing the result of the operation back on the stack. So after you've parsed the ABCD, you have four things on the stack waiting for later operations.
 
  • #3
What needs to be parsed? AB on the left and CD on the right?
 
  • #4
Bucs44 said:
What needs to be parsed? AB on the left and CD on the right?

?? Neither. I can't start drawing a tree until I hit the +, at which point I realize C and D are leaves of the + node. Then the + node is itself a leaf of the * node, to get the other leaf I go back and see what's on the stack and there is a B etc etc.
 
  • #5
(This belongs into the computer homework section.)

It might be instructive for you to work out the equivalent infix expression.
 

Related to Solving a Postfix Expression: ABCD+*/E- Tree

1. What is a postfix expression?

A postfix expression is a mathematical notation where the operator is placed after the operands. For example, the expression "3 + 5" would be written as "3 5 +".

2. How do you solve a postfix expression?

To solve a postfix expression, you need to follow these steps:

  • Start from the left and read the expression one character at a time.
  • If the character is a number, push it onto a stack.
  • If the character is an operator (+, -, *, or /), pop the top two numbers from the stack and perform the operation on them. Push the result back onto the stack.
  • Continue reading and performing operations until you reach the end of the expression.
  • The final result will be the only number left on the stack.

3. What is a postfix expression tree?

A postfix expression tree is a binary tree where the operators are represented as the internal nodes and the operands are represented as the leaf nodes. The tree is built by following the same steps as solving a postfix expression, but instead of using a stack, the nodes are created and connected to their corresponding operators and operands.

4. How do you create a postfix expression tree?

To create a postfix expression tree, you can follow these steps:

  • Start from the left and read the expression one character at a time.
  • If the character is a number, create a leaf node with that number.
  • If the character is an operator (+, -, *, or /), create a new node with that operator as its value.
  • Pop the top two nodes from the stack and make them the children of the new node.
  • Push the new node onto the stack.
  • Continue reading and creating nodes until you reach the end of the expression.
  • The final node on the stack will be the root of the postfix expression tree.

5. What is the significance of solving a postfix expression?

Solving a postfix expression is important because it allows us to evaluate complex mathematical expressions in a structured and efficient manner. It also helps in converting an infix expression (where the operator is placed between the operands) to a postfix expression, which is easier to evaluate. Postfix expression trees are also useful in solving other mathematical problems such as evaluating prefix expressions and converting between different types of notation.

Similar threads

Differential equation tree height
    • Calculus and Beyond Homework Help
Replies
3
Views
2K
How long has the tree been dead?
    • Calculus and Beyond Homework Help
Replies
5
Views
2K
Solve ##\int\frac{e^{-x}}{x^2}dx## and ##\int \frac{e^{-x}}{x}dx##
    • Calculus and Beyond Homework Help
Replies
7
Views
740
Vector Geometry: Quadrangular Pyramid with Inner and Cross Products
    • Calculus and Beyond Homework Help
Replies
1
Views
1K
How to show that this expression with tensors reduces to zero?
    • Calculus and Beyond Homework Help
Replies
6
Views
596
B Probably a silly question about tree diagrams
    • Set Theory, Logic, Probability, Statistics
Replies
16
Views
2K
Algorithm for computing the depths of all the nodes of tree
    • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
Intuition about simplifying this expression
    • Calculus and Beyond Homework Help
Replies
2
Views
825
Can Any Decision Tree Be Converted into DNF?
    • Calculus and Beyond Homework Help
Replies
1
Views
2K
Array-list implementation of tree problem
    • Engineering and Comp Sci Homework Help
Replies
3
Views
2K

Hot Threads

Recent Insights

Back
Top