Infix to Postfix notation C++ [duplicate]

Question

This question already has answers here:

Convert from an infix expression to postfix (C++) using Stacks (6 answers)

Closed 8 years ago.

Hello Stack I'm curently atempting to write a RPN converter and I'm new to C++. But I'm running into problems. Hopefully I can explain the problems in detail. Im using an array for stacking my operators. Lets use the example "5 + 8" When I get down to:

else if(infix[i] == '+' or infix[i] == '-' or infix[i] == '*' or infix[i] == '/' or infix[i] == '^'){
                while(isp(stack1.top()) >= icp(infix[i])){
                    postfix += stack1.pop();
                }
                if(isp(stack1.top()) < icp(infix[i])){
                    stack1.push(infix[i]);      
                }

For some reason it will push the operator onto the stack but then it wont add the operator to the postfix string variable that im adding my elements too. the out put woul be like "5 8" I looked at my pop function and that seems to be correct but im stumped. if you can lead me in the right direction that would be great.

This is my full code:

#include <iostream>
#include <string>
#define DEFAULT_SIZE 100

using namespace std;

class Stack{

private:
    char *array;
    int tos, capacity;

public:
    //constructors
    Stack();

    //Destructor
    ~Stack();

    //Methods
    void push(char a);
    char pop();
    char top();
    int get_size();
    bool is_empty();
    bool is_full();
    void display();    

};

Stack::Stack(){
    array = new char[DEFAULT_SIZE];
    tos = 0;
    capacity = DEFAULT_SIZE;
}

Stack::~Stack(){
    delete[] array;
}

void Stack::push(char a){
    if(!is_full())
        array[tos++] = a;
}

char Stack::pop(){
        return array[--tos];
}

char Stack::top(){
    return array[tos];
}

int Stack::get_size(){
    return tos; 
}

bool Stack::is_empty(){
    if(tos == 0)
        return true;
    else
        return false;
}

bool Stack::is_full(){
    if(tos == capacity)
        return true;
    else
        return false;
}

void Stack::display(){
    if (tos == 0)
        cout<<"The stack is empty"<<endl;
    else{
        for (int i=0; i<tos;i++)
                cout<<array[i]<<" ";
        cout<<endl;        
    }
}

int isp(char a){
    if(a == '^'){
        return 3;
    }
    else if (a == '*' or a == '/'){
        return 2;
    }
    else if(a == '+' or a == '-'){
        return 1;
    }
    else if(a == '('){
        return 0;
    }
    else
        return -1;
}

int icp(char a){
    if(a == '^'){
        return 4;
    }
    else if (a == '*' or a == '/'){
        return 2;
    }
    else if(a == '+' or a == '-'){
        return 1;
    }
    else if(a == '('){
        return 4;
    }
}



int main(){
    string infix, postfix;
    Stack stack1;

    cout << "This is a Infix to Postfix Expression converter." << endl;
    cout << "Enter your Infix Expression: ";
    cin >> infix;
    stack1.push('#');

    for(int i=0;i<infix.length();i++){
        if(isdigit(infix[i]) or isalpha(infix[i])){
            postfix += infix[i];
        }
        else if(infix[i] == '+' or infix[i] == '-' or infix[i] == '*' or infix[i] == '/' or infix[i] == '^'){
            while(isp(stack1.top()) >= icp(infix[i])){
                postfix += stack1.pop();
            }
            if(isp(stack1.top()) < icp(infix[i])){
                stack1.push(infix[i]);      
            }
        }
    }
    cout << postfix;


    return 0;
}

Also if you know anygood resource sites on C++ RPN converter feel free to share because it would be a very big help! Im going off a random algo. that I found on google.

Answer 1

With your example, you're just pushing the "+" sign on the stack, but you never pop it because after processing the symbol "8", you've left the for loop. I think you need another while loop to empty your stack at the end.

for(int i=0;i<infix.length();i++){
    if(isdigit(infix[i]) or isalpha(infix[i])){
        postfix += infix[i];
    }
    else if(infix[i] == '+' or infix[i] == '-' or infix[i] == '*' or infix[i] == '/' or infix[i] == '^'){
        while(isp(stack1.top()) >= icp(infix[i])){
            postfix += stack1.pop();
        }
        if(isp(stack1.top()) < icp(infix[i])){
            stack1.push(infix[i]);      
        }
    }
}

// Fetch the remaining operators from the stack
while(!stack1.is_empty()){
    postfix += stack1.pop();
}

cout << postfix;

Beware of bugs, as I couldn't test this code myself.