Results 1 to 4 of 4

Math Help - Help with postfix expression problem

  1. #1
    Newbie
    Joined
    Apr 2014
    From
    New York
    Posts
    1

    Question Help with postfix expression problem

    I need to figure out the value of this postfix expression

    3 2 * 2 ↑ 5 3 - 8 4 / * -

    Can someone help?
    Thanks, I'm new here
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Help with postfix expression problem

    Welcome to the forum. For a reasonable price, I can sell you an HP 50g calculator that uses reverse polish notation. You can enter this expression and get the result. Just kidding.

    Why don't you read the algorithm for evaluating a postfix expression and the following example? I think the explanation is pretty clear.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    709
    Thanks
    294

    Re: Help with postfix expression problem

    Hi,
    If you don't know about the stack data structure, you can quit reading now.
    Otherwise, here's my description of the algorithm:

    Assume all operands (as in your example) are single digit integers. For a valid postfix expression, scan the string from left to right.

    1. If the current token is an operand, push it.
    2. If the current token is an operator, pop the two operands (first pop is second operand), perform the operation and push the result.
    3. At the end of the scan, the one value on the stack is the value of the expression.

    Examples:

    1. 5 2 -: push 5, push 2, pop 2 pop 5, compute 5-2=3 and push 3. Value is 3.
    2. 2 3 4 * + 2 3 ^ +: push 2, push 3, push 4, pop 4, pop 3, push (3*4=12), pop 12, pop 2, push(2+12=14), push 2, push 3, pop 3, pop 2, push(2^3=8), pop 8, pop 14, push(14+8=22), Value is 22.

    For long expressions, it may help to draw the contents of the stack at each stage. Finally, the above algorithm also detects errors in the expression: if at any point, an operator that requires two operands is encountered, but there is only one value on the stack, then expression error. Also at conclusion, if there is not exactly one operand on the stack, again error.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Sep 2009
    Posts
    40
    Thanks
    5

    Re: Help with postfix expression problem

    A good way to visualize your expression is with a binary tree. The operator is the third term in every expression. So starting, we have:
    *
    / \
    3 2

    We then treat this cluster (3 2 *) as a single value. So we have ((3 2 *) 2 ^). Again, the carat is the root of a tree with the left child as * and the right child as 2.

    We then examine (5 3 *), which we construct as its own binary tree. We do the same for (8 4 /). The * operator in ( (5 3 *) (8 4 /) *) tells us that * is the root for these two binary trees. Finally, we connect the - operator to the carat and * operators.

    The algorithm is great if you are programming a solution for this. The binary tree is quite easy to visualize. In essence, the algorithm is using stacks and queues to traverse a binary tree structure without having the physical node-based backbone present. This is one of Dijkstra's algorithms, though not the famous shortest path algorithm. Hope this helps some!

    Help with postfix expression problem-expression_tree.jpg
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: November 29th 2012, 04:59 PM
  2. Expression problem
    Posted in the Algebra Forum
    Replies: 2
    Last Post: October 23rd 2010, 10:06 AM
  3. Postfix notation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 20th 2009, 08:13 AM
  4. convert any infix epression/equation to postfix `
    Posted in the Math Software Forum
    Replies: 0
    Last Post: October 16th 2008, 09:28 PM
  5. an expression problem
    Posted in the Algebra Forum
    Replies: 1
    Last Post: December 7th 2007, 10:45 AM

Search Tags


/mathhelpforum @mathhelpforum