So here is the assignment I have to complete within the next hour that I've procrastinated way too long on doing. If someone can just kind of guide me along in the process I'd be very grateful. I haven't done coding in a while so I just need my memory refreshed as I won't learn anything if I'm given the answer.
Assignment:
Implement the following infix-to-postfix algorithm in C++. Make sure you understand the algorithm by going through a few examples with pencil and paper, only then start implementing it. Note the indentation implies the beginning and end of a block of code.
Determine the time complexity of the algorithm.
This algorithm can be modified by adding one more stack to evaluate expressions. Think about how you would do that.
Hand in a printout of your program and a typescript of sample runs.
Code:
// An algorithm for infix to postfix expression conversion.
// For example, a + b - c translates to a b + c -
// a + b * c translates to a b c * +
// (a + 2) / (5 + d) goes to a 2 + 5 d + /
// Valid operands are single digits and characters: 0-9, a-z, A-Z
// Valid operators are: +, -, *, /, (, )
// Highest precedence: * /
// Lowest precedence: + -
// ) never goes on stack.
// ( has lowest precedence on the stack and highest precedence outside of stack.
// Bottom of the stack has the lowest precedence than any operator.
// Use a prec() function to compare the precedence of the operators based on the above rules.
// Note there is little error checking in the algorithm!
while there is more input
if input is an operand
print input
elseif input is '(' // '(' has lowest precedence in the stack, highest outside
push input on stack
elseif input is ')'while stack is not empty and top of stack is not '('
print top of stack
pop stack
if stack is not empty
pop stack
else error // no matching '('
elseif stack is empty or prec(top of stack) < prec(input) // bottom of stack has lower precedence than everything
push input on stack
elseif prec(top of stack) >= prec(input)
while stack is not empty and prec(top of stack) >= prec(input)
print top of stack
pop stack
push input on stack
else check for errors
while stack is not empty
print top of stack
pop stack
Make sure you understand the algorithm by going through a few examples with pencil and paper, only then start implementing it. (...)
Determine the time complexity of the algorithm.
¿Did you do that?
Some translations
1 2 3
while( cin>>input ) //while there is more input
if( isalnum(input) ) //if input is an operand (A-Za-Z0-9) you may want to implement it
cout << input; //print input