I'm stuck at comparing the operators, it seems I can only compare the current operator to the topmost of the stack, how do I keep on comparing it til the stack is null or the precedence don't hold true anymore?...i've commented the part where I think my program fails...any help?

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

void push(char);
char pop(char);
int prec(char);

struct node{
    string mdas;
    node *nxt;
};

node *start=NULL;
string postf;

int main(){
    string inf;
    const char *p;
    const char *q;

    cout<<"Enter string: ";
    cin>>inf;

    p = inf.c_str();

    while(*p!='\0'){
        if(*p!='+' && *p!='*' && *p!='/' && *p!='-'){
            postf.push_back(*p);
        }
        else{
            if(start==NULL)
                push(*p);
            else{
                    q = start->mdas.c_str();
                /*if(prec(*q)>prec(*p)){
                    postf.push_back(pop(*q));
                }
                else
                    push(*p);*/
                cout<<prec(*q)<<" "<<prec(*p)<<endl;
            }
        }
        p++;
    }

    cout<<postf<<endl;
    while(start!=NULL){
        cout<<start->mdas<<" ";
        start = start->nxt;
    }
    cout<<endl;
    return 0;
}

void push(char p){
    node *temp;

    temp = new node;
    temp->mdas.push_back(p);

    if(start==NULL){
        start = temp;
        start->nxt = NULL;
    }
    else{
        temp->nxt = start;
        start = temp;
    }
}

int prec(char a){
    switch(a){
        case '+':
        return 1;
        break;

        case '-':
        return 1;
        break;

        case '/':
        return 2;
        break;

        case '*':
        return 2;
        break;
    }
}

char pop(char b){
    node *del;
    del = start;
    start = start->nxt;
    delete del;
    return b;
}

Edited 4 Years Ago by letterG

This will do it.

  //Hanlding the operator part.
  else {
            if(start==NULL)
                push(*p);
            else {
                node *temp = start;
                while(temp)
                {

                  q = temp->mdas.c_str();
                  temp = temp->nxt;
                  if(prec(*q)>prec(*p))
                     postf.push_back(pop(*q));
                  else break;
                }
                push(*p);

        }

how do I keep on comparing it til the stack is null or the precedence don't hold true anymore?

Use a loop. ;) The algorithm should look something like this:

for each character
    if whitespace
        next
    else if not an operator
        append the current character to postfix
    else
        until the stack is empty or the top value has greater or equal precedence
            append the top item
        push the current character to the stack

until the stack is empty
    append the top item

Which when converted to C++ might look like this:

std::string InfixToPostfix(const std::string& infix)
{
    std::stack<char> st;
    std::string result;

    for (char ch : infix) {
        if (isspace(ch))
            continue;
        else if (!IsOperator(ch))
            result.push_back(ch);
        else {
            while (!st.empty() && ComparePrecedence(st.top(), ch) >= 0) {
                result.push_back(st.top());
                st.pop();
            }

            st.push(ch);
        }
    }

    while (!st.empty()) {
        result.push_back(st.top());
        st.pop();
    }

    return result;
}

This is all without handling parentheses, of course, but your code didn't either.

thanks for the replies, turns out I only needed to pop the topmost part of the stack, not the whole thing. :D

This question has already been answered. Start a new discussion instead.