infix to postfix conversion

[koopey]

tyring to find the bug for last 1.5hrs. can't find whats wrong! overlook the cout statements that i used to trace the bug.right answer: abcd^e-fgh*+^*+i- what i get: abcde-^(*+fgh*+(i )-i

  #include <iostream>
#include <string>
using namespace std;

struct stack
{
    int top;
    char* array;

};

stack* make_stack(int size)
{
    stack* Stack=new stack;
    Stack->array=new char[size];
    Stack->top=-1;
    return Stack;

}

char push(stack* Stack, char op)
{
    Stack->array[++Stack->top]=op;
    cout<<"first value: "<<Stack->top<<endl;
}

char pop(stack* Stack)
{
    return Stack->array[Stack->top--];
}

char peek(stack* Stack)
{
    return Stack->top;
}


bool isempty(stack* Stack)
{
    return Stack->top==-1;
}

bool isoperand(char op)
{
    return ((op>='a'&&op<='z')||(op>='A'&&op<='Z'));
}

//precedence func
int prec(char opt)
{
    switch(opt)
    {
        case '+':
        case '-':
            return 1;break;
        case '*':
        case '/':
            return 2;break;
        case '^':
            return 3;break;
    }
    return -1;//char isn't operator
}


string infixtopostfix(string& exp)
{
   stack* Stack= make_stack(exp.length());
    int k=0;
    for(int i=0;i<exp.length();i++)
    {
        if(isoperand(exp[i]))
                {exp[k++]=exp[i];cout<<"1";}
        else if(exp[i]=='(')
                {push(Stack,exp[i]);}

        else if(exp[i]==')')
                {
                    while(!isempty(Stack) &&peek(Stack)!='(')
                          {exp[k++]=pop(Stack);cout<<"done";}
                          if (!isempty(Stack) && peek(Stack) != '(')
                return exp; // invalid expression
            else
                pop(Stack); 
                       // pop(Stack);//one more pop to remove '('
                }
        else
        {
            cout<<"2";
            while(!isempty(Stack)&&prec(exp[i])<=prec(peek(Stack)))
                    {exp[k++]=pop(Stack);cout<<"3";}

                push(Stack,exp[i]);
        }
        cout<<"i value: "<<i<<endl;
    }
    while(!isempty(Stack))
    exp[k++]=pop(Stack);
    exp[k]='\0';
    return exp;
}

int main()
{
    string exp="a+b*(c^d-e)^(f+g*h)-i";
    cout<<infixtopostfix(exp);



}

[Bdanielz]

Can you explain why or what makes this input ""a+b*(c^d-e)^(f+g*h)-i";" imply " abcd^e-fgh*+^*+i-" is a correct awnser? I am not following what you are trying to do here.

[koopey]

Am into data structure recently. Its an application of stack.
http://geeksquiz.com/stack-set-2-infix-to-postfix/

Algorithm
1. Scan the infix expression from left to right.
2. If the scanned character is an operand, output it.
3. Else,
…..3.1 If the precedence of the scanned operator is greater than the precedence of the operator in the stack(or the stack is empty), push it.
…..3.2 Else, Pop the operator from the stack until the precedence of the scanned operator is less-equal to the precedence of the operator residing on the top of the stack. Push the scanned operator to the stack.
4. If the scanned character is an ‘(‘, push it to the stack.
5. If the scanned character is an ‘)’, pop and output from the stack until an ‘(‘ is encountered.
6. Repeat steps 2-6 until infix expression is scanned.
7. Pop and output from the stack until it is not empty.

If it helps the my code is mostly similar but still cant find the damn error! :(

[Chervil]

See also the topic of Reverse Polish Notation
http://www-stone.ch.cam.ac.uk/documentation/rrf/rpn.html
http://www.calculator.org/rpn.aspx

[koopey]

@chervip the links are exact same things as infix to postfix but i am having problem with the code above. :(

[Chervil]

Yes, my reply was really in response to the question by Bdanielz.

I started to look at the code. One thing which seems very confusing is that the function infixtopostfix() is modifying the input string exp even before it has finished reading from it. That seems risky, at the very least. So the first thing I'd suggest is to use separate strings for the input and output processing. Since the input and output strings may be of differing lengths, I'd suggest, instead of

int k=0;
exp[k++]=exp[i];

something like this would be better:

string output;
output += input[i];

etc.


Also, just running a quick test on the original code, the input string exp = "a*(b+c)"; gives an infinite loop in the while loop at line 97.

There is an error in function peek, instead of

char peek(stack* Stack)
{
    return Stack->top;
}

it should be:

char peek(stack* Stack)
{
    return Stack->array[Stack->top];
}

[koopey]

@Chervil Bull's eye! those two suggestions perfectly solved the problem.thanks!
but another thing. how did u know there was an infinite loop at line 97 but then found the problem was at "peek" function. did you use debugging tools or just looked at code? i dont know debugging, so curious...

[48T7M4Gy]

http://www.cplusplus.com/forum/beginner/192566/

[Chervil]

but another thing. how did u know there was an infinite loop at line 97 but then found the problem was at "peek" function. did you use debugging tools or just looked at code? i dont know debugging, so curious...

Well, at first, I didn't bother to study the code at all, except to notice a few warnings issued from the compiler which already hinted at the problem. Function peek was supposed to return a char but was trying to return an int. I suppose that was enough of a clue, and I could have figured it out without even running the program. But that would have involved understanding the code and since I wasn't the author, it involved getting to grips with the design and how it was supposed to work. At that point I decided to start running the program with different test data.

I just ran it with different input strings, first just "a", then "a+b" and so on ... in this way I planned to isolate which type of string was causing problems.

When I did hit a problem, the program simply crashed with a bad return code. From there I started to use a debugger. Immediately it reported on the last line executed before the crash, was the loop at line 97. Now I was prepared to actually look at the code. I wanted to know what was the contents of the different variables.

Before I started running with the debugger, I changed the program to use separate input and output strings, that made debugging easier to understand - though it's not normal practice to change the code before debugging it! But I wasn't even sure whether that change might fix the problem (it didn't - though it solves some other issues).

So the last thing was to step through the code line by line looking at the contents of various variables. Somewhere in that process it started to become clear ...

With hindsight, none of this was necessary, I could have simply looked at the geeksquiz link provided above and compared the sample code there with the code in this post.

[koopey]

@kemort yes that's my post again but,..." what do you mean....tu du du... you nod your head yes but you wanna say no!" ;) copyright: justin bieber. hehe
@chervil thanks a lot! :)