CODEWITHSUNDEEP
c++queuepostfix-notation
user2130537
user2130537

Reputation: 27

Need to create infix to postfix algorithm

I need to implement infix to postfix conversion algorithm to compute the expression a+b*c-d/e

I also need to do this using queue (I believe 2 different queue stacks are needed)

I've created my queue class using a DoubleLinkList and now just need to create the algorithm for this problem. I'm pretty lost on how to go about it, though. Any help would be appreciated!

so far(And I know it's very wrong) I have:

string infix = "a+b*c-d/e";
    Queue *holder = new Queue();
    Queue *newstring = new Queue();
    int length = infix.length();
    char temp;
    char prev;
    for(int i=0; i<length; i++)
    {
        temp = infix[i];
        if((temp == '+') || (temp == '-') || (temp == '*') || (temp == '/'))
        {
            if (holder->isEmpty())
            {
                holder->queue(temp);
            }
            if(temp<holder.enqueue())
            {

            }
        }
        holder->queue(temp);

    }

Upvotes: 0

Views: 3462

Answers (2)

Thomas Matthews
Thomas Matthews

Reputation: 57698

I think you should create a tree of operators and values.
You can convert from infix to postfix to prefix depending on your traversal order of the tree.
Your instructor may have give you assignments to convert between the three.

Here are some articles:
University of Texas
YouTube video
Wikipedia - Expression trees

Upvotes: 0

Barney
Barney

Reputation: 2373

I assume this is a homework assignment so it is important that you figure out the programming details on your own. The general outline of the algorithm is as follows:

Define a stack
Go through each character in the string
If it is between 0 to 9, append it to output string.
If it is left brace push to stack
If it is operator *+-/ then 
          If the stack is empty push it to the stack
          If the stack is not empty then start a loop:
                             If the top of the stack has higher precedence
                             Then pop and append to output string
                             Else break
                     Push to the stack

If it is right brace then
            While stack not empty and top not equal to left brace
            Pop from stack and append to output string
            Finally pop out the left brace.

If there is any input in the stack pop and append to the output string.

Upvotes: 2

Related Questions