1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: C++ data structures please help

  1. Oct 29, 2007 #1
    c++ data structures!! please help!!!

    i want to write a c++ program that implements a binary search tree from an infix expression. the program should perform the following:
    -the expression should be saved and read from a file.
    -use a stack to check if the expression is well formed in terms of brackets, '([{', and their counterparts.
    -construct an expression tree from the expression.
    -if there is a problem in the expression tree then the program should tell exactly where the imbalance is.
    -validate your input to accept only numbers and operators.
    -evaluate the expression tree.(Not the infix expression)
    -traverse the expression tree with the three traversal strategies to produce the appropriate expressions.
    -print the tree.
    -use a linked approach for your solution
  2. jcsd
  3. Oct 29, 2007 #2
    This is a decent-sized project. I wrote this exact thing many years ago (and still have the code, but I'm keeping it to myself), so I can probably help as my time permits (I get sudden bursts of work). But there is obviously a lot to this so I don't want to compose a big post only to find you already knew most of what I wrote. I'll be glad to ramble, though, if you assure me you have no idea where to start--or did you have any specific questions?
  4. Oct 29, 2007 #3
    thanx for the reply and your time! i do very much appreciate your help. the problem is that i have to submit the assignment before the 5th of november and i dont have a clue where to start. can you kindly help me with the code
  5. Oct 29, 2007 #4
    thanx for the reply and your time! i do very much appreciate your help. the problem is that i have to submit the assignment before the 5th of november and i dont have a clue where to start. can you kindly help me with the code
  6. Oct 29, 2007 #5

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    We are here to help you. Giving out the answers does not help you learn anything. You must have been taught something regarding this problem. I will help a bit by asking some leading questions:
    • What rules of arithmetic does your parser have to be able to handle? In other words, does it have to handle associativity (1+2+3=6) and precedence (1+2*3=7)?
    • What operators does your parser have to be able to handle?
    • Does your parser have to be able to handle negative numbers?
    • Do you have to be able to detect ill-formed expressions such as "* 2", or just problems with imbalanced parentheses?
    • Have you been taught what BNF means? If so, have you written a BNF for your parser? (This is a very good place to start).
  7. Oct 29, 2007 #6
    This is a several-step process. I've included the basics here:

    (Note that if you are familiar with regular expressions and have some regex code, that can help simplify some code. If you aren't familiar with regex, don't bother learning it now--it isn't all that necessary)

    First, preprocess the infix for unary operators. A unary operator is a minus or plus that is NOT preceded by a close parentheses or a value. When you find a term preceded by a unary operator, insert a '0' in front of it and then enclose the term with parentheses. For example, change...

    (3 + -4 + 5)
    (3 + (0-4) + 5)

    For another example, convert

    (5 + -(3+2))
    (5 + (0-(3+2)))

    As you can see, when you do find a unary operator, you must go forward to find the end of the term--even if the term is a parenthetical expression. Generally you do this by moving forward through the characters and incrementing a variable each time you pass a '(' and decrementing it when you pass a ')'.

    Of course, unary +'s can simply be removed or replaced with a space.

    Next, compile the infix expression to a postfix (reverse Polish) program. For example, the postfix program for the infix expression...

    (3 * (4 - sin(5)))

    ...is this:

    Push a 4
    Push a 5
    Sin (this pulls one number off the stack and pushes its sine)
    Subtract (this pulls two numbers off the stack and pushes their difference)
    Push a 3
    Multiply (this pulls two numbers off the stack and pushes their product)

    Your compiler would be a recursive function call that takes a pointer (or index) to the beginning of a (sub)expression, appends the reverse Polish instructions to the current program, and then returns.

    Let's say the function is called "CompileExpression". So CompileExpression does the following:

    1. Find the end of the expression (by counting open & close parentheses)

    2. If the incoming expression is just a value, append a 'push value' instruction to the current program and return.

    3. If the incoming expression is a function call (like 'tan(3+4)'), call CompileExpression for the parameter, append to the program the instruction for the function, and then return.

    4. Find the character positions of the main binary operator and its two terms. For example, in the expression (3 * (4 - sin(5))), the first term is '3', the main operator is '*', and the second term is '(4-sin(5))'

    5. Call CompileExpression recursively to compile each term.

    6. Append the reverse Polish instruction for the main operator onto the current program.

    7. Return

    To write your reverse Polish interpreter, you need simply create a stack, and execute the instructions sequentially (they'll push & pop things on that stack). Make sure your stack pointer==1 after the program runs. After the program executes, the single value on the stack is your answer.
  8. Oct 29, 2007 #7
    I forgot to make clear in the previous post: You do not execute the reverse Polish instructions as you discover them. you put the instructions in an instruction buffer so that you can execute them later (with the interpreter). One advantage of this is that when you eventually support variables, you can execute the same program using different variables.

    By the way, if you want to add variable support in the future, convert all values into variables (even the constants in the expression) and push their addresses onto the stack instead of the actual values. That way the interpreter need simply consider everything a variable--it always knows stack contents are addresses.
    Last edited: Oct 29, 2007
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook