c++ - Infix to Postfix Output program

Question

I am a novice C++ programmer. I have written the following C++ code for infix to postfix expressing using an array-based stack, however, I get ^2 in string each time and also I can't figure out why my answer is not correct.

I can't find the logical error either. Can someone please help me with this?

#include<iostream>
#include <string>

using namespace std;
using std::string;

class stack {
public:
    int top;
    char* astack;
    int size;
    stack(int s) {
        size = s;
        top = -1;
        astack = new char[size];
    }
    void Push(char element);
    char Pop();
    bool isEmpty();
    bool isFull();
    char Peek();
    void clear();
    void print(stack* ptr);
};

char stack::Peek() {
    if (isEmpty()) {
        return 0;
    }
    return astack[top];
}

void stack::clear() {
    top = -1;
    delete astack;
    astack = new char(size);
};

void stack::Push(char element) {
    if (isFull()) {
        cout << "The stack is already Full" << endl;
        return;
    }
    else
        astack[++top] = element;
    return;
}

char stack::Pop() {
    if (isEmpty()) {
        cout << "The Array is already empty" << endl;
    }
    else {
        return astack[--top];
    }
}

void stack::print(stack* ptr) {
    for (int i = 0; i < ptr->top; i++) {
        cout << ptr->astack[i];
    }
}

bool stack::isEmpty() {
    if (top == -1) {
        return 1;
    }
    return 0;
}

bool stack::isFull() {
    if (top == size - 1) {
        return 1;
    }
    return 0;
}

int precedence(char element) {
    int weight = -1;
    switch (element) {
    case '+':
    case '-':
        weight = 1;
    case '*':
    case '/':
        weight = 2;
    case '$':
        weight = 3;
    }
    return weight;
}

bool IsOperator(char C) {
    if (C == '+' || C == '-' || C == '*' || C == '/' || C == '$')
        return true;
    return false;
}

bool IsOperand(char C) {
    if (C >= '0' && C <= '9') return true;
    if (C >= 'a' && C <= 'z') return true;
    if (C >= 'A' && C <= 'Z') return true;
    return false;
}

int main() {
    string infix;
    getline(cin, infix);

    int j = 1;

    string post = "";

    stack* postfix = new stack(50);
    for (int i = 0; i != infix.size(); i++) {
        char element = infix[i];
        if (IsOperand(element)) {
            post += element;
        }
        if (IsOperator(element)) {
            if (precedence(element) >precedence(postfix->Peek())) {
                postfix->Push(element);
            }
            else {
                while (precedence(element) <= precedence(postfix->Peek())) {
                    if (precedence(element) < precedence(postfix->Peek())) {
                        post += postfix->Pop();
                    }
                    if (precedence(element) == precedence(postfix->Peek())) {
                        cout << postfix->Peek() << endl;
                        post += postfix->Pop();
                    }
                }
            }
        }
    }

    while (!postfix->isEmpty()) {
        post += postfix->Pop();
    }

    cout <<"Postfix expression is : "<< post;
}

The output is attached below:

Expected output: 576/1*-6+

I can't figure out why it has ^2 in output instead of operator symbols and also the answer is different. Please help me with this.

question from:https://stackoverflow.com/questions/65641451/infix-to-postfix-output-program

Answer 1

Starting off, I just want to point out that the use of classes is for data hiding. Making your top, size, and other data members of public scope completely defeats the purpose. Secondly, the nomenclature of classes should start with an uppercase alphabet.

The first error is with your stack::Push(char) method. Note the difference between return astack[--top] and return astack[top--]. The former decreases the value of top by 1, and then returns the value, whereas, the latter returns the value of astack[top] and then decrements top.

This is very crucial as what you really want is to return the value popped, and not the value at the top of the stack after popping.

char stack::Pop() {
    if (isEmpty()) {
        cout << "The Array is already empty" << endl;
    }
    else {
        // Note the change here.
        return astack[top--];
    }
}

Furthermore, since stack::print(stack *) is a method of the class, every instance has its own copy for this member function. There is no need to explicitly pass an instance of stack to it. You can achieve this by the following piece of code:

void stack::print() {
    for (int i = 0; i <= top; ++i) {
        cout << astack[i];
    }
    
    cout << "
";
}

Coming over to your precedence(char) function, you need to break out of a switch condition when your goal is achieved.

int precedence(char element) {
    switch (element) {
        
        case '+': return 1;
        case '-': return 1;
        case '*': return 2;
        case '/': return 2;
        case '$': return 3;
        
        default: return -1;
    }
}

Moving onto your algorithm of converting infix to postfix, you have to keep popping all same or higher priority operators from the stack, and then push your scanned operator.

if (IsOperand(element)) {
    post += element;
}
else if (IsOperator(element)) {
    if (precedence(element) > precedence(postfix->Peek())) {
        postfix->Push(element);
    }
    else {
        while (precedence(element) <= precedence(postfix->Peek())) {
            post += postfix->Pop();
        }
        
        postfix->Push(element);
    }
}

I would suggest a few more changes such as adding to check for parantheses, but that seems to be out of the scope of this question. Good luck!