Converting from Infix to Postfix using stacks (c++)

Question

I'm currently working on a project to convert from postfix to infix using a stack in the form of a singly linked list. I've managed to convert expressions such as ab+ to (a+b) however when the expression gets longer such as ab+cd*-. It doesn't work. I'm considering pushing the previously converted expression back onto the stack however the stack is of type char and the expression is a string and it complains when I try to push it back. Should I make it a template and if so how would I do it or is there anyway else to solve this problem.

Here is my code:

#include "stack.h"

void convert(string expression){
    stack c;
    string post = " ";
    string rightop = "";
    string leftop = "";
    string op = "";

    for (int i = 0; i <= expression.length(); i++){
        c.push(expression[i]);
        c.print();
        if (expression[i] == '*' ||
            expression[i] == '+' ||
            expression[i] == '-' ||
            expression[i] == '/'){
            cout << c.top() << endl;
            leftop = c.top();
            cout << leftop << endl;

            c.pop();

            rightop = c.top();
            cout << rightop << endl;
            c.pop();
            op = c.top();
            cout << op << endl;
            //c.pop();
            post = "(" + leftop + " " + op + " " + rightop + ")";

            cout << post << endl;
        }
        //c.push(post);
    }
}


int main(){   
    string expression;
    cout << " Enter a Post Fix expression: ";    
    getline(cin, expression);    
    convert(expression);    
    return 0;
}

Since you want to convert whole expressions to infix notation, your stack must be able to hold entire expressions, not just characters. That is, whenever you parse an expression, you must push it unto the stack. You can push an entire expression one character at a time, provided you delimit them with the parenthesis, but then you have a complication of counting the open parenthesis and so on — TheCppZoo, Jun 26 '15 at 18:20

score 0 · Answer 1 · edited May 23 '17 at 12:15

The original code is lacking following declarations to compile :

#include "stack"
#include "string"
#include "iostream"

using namespace std;

Next, the type of the stack should be a string to be able to store full expressions onto it.

You did not take the elements in proper order from the stack : it is first op, next rightop and finally leftop

The currently commented out last c.pop() is necessary to remove 3rd element from the stack, but it must be followed inside the loop with the (again commented out) c.push(post);

The loop on expression goes one step too far : it should be for (int i =0; i<expression.length();i++) (note the < instead of <=)

When this is done, it is enough to make the convert function to return the last post as a string for the program to give expected result.

As you asked in this other question, it would be much better to ignore spaces in the input string : you should add if (isspace(expression[i])) continue; immediately after the for.

With all those fixes, the code could be :

#include <stack>
#include <string>
#include <iostream>
#include <cctypes>

using namespace std;

string convert(string expression){

    stack<string> c;

    string post =" ";
    string rightop="";
    string leftop="";
    string op ="";

    for (int i =0; i<expression.length();i++){
        if (isspace(expression[i])) continue;
        c.push(string(expression.c_str() + i, 1));
        //c.print();
        if(expression[i] == '*' ||
            expression[i] == '+' ||
            expression[i] == '-' ||
            expression[i] == '/'){
                cout<<c.top()<<endl;
                op=c.top();
                cout<<leftop<<endl;

                c.pop();


                rightop=c.top();
                cout<<rightop<<endl;
                c.pop();
                leftop=c.top();
                cout<<op<<endl;
                c.pop();
                post="(" + leftop + " " + op + " " + rightop + ")";

                cout<<post<<endl;
                c.push(post);
        }
    }
    return post;
}

int main(){

    string expression;
    cout<<" Enter a Post Fix expression: ";

    getline(cin,expression);

    string converted = convert(expression);

    cout << "Converted expression : " << converted << endl;

    return 0;
}

And when given ab+cd*- you get at the end ((a + b) - (c * d))

You just have to comment out all the traces form convert method ;-)

The inclusions which you stated were included in a .h file which wasn't shown because I didn't want to overwhelm the reader.I can't place the stack as type string as it complains when I want to push the character onto it. The pop doesn't work at the last instance that's why I left it out. Thank you for response but you literally mentioned errors which I already have the answers to and told me to solve my original problem I asked as an exercise. — Kharl Mccatty, Jun 26 '15 at 20:03
@KharlMccatty : I already solved the biggest part of your problem :-) . My code compiles and run. I convert the character into string with `string(expression.c_str() + i, 1)` to be able to push it onto stack. And the last `pop` works, provided you follow it inside the loop with the `c.push(post);`. I could not know that you had already fixed those problems. I only listed them to explain my changes to original code. Anyway, I've just rewrote my answer because it was indeed unnecessary rude. I apologize for that, but was angry because it took me time to compile the code :-( — Serge Ballesta, Jun 26 '15 at 21:16

AndersK · Answer 2 · 2015-06-26T22:17:32.990

i get the impression your "stack" is not used properly. e.g. if ab+* is pushed on the stack your variables become leftop = +, rightop = b, op = a, in order to convert a postfix expression it is easiest to create a binary evaluation tree to get the operator precedence right

e.g.

for ab+c* you want

     *
    / \
   +   c
  / \
 a   b

and then evaluate the tree either recursively or not. everytime the operator is + or - use parenthesis around it,

Converting from Infix to Postfix using stacks (c++)

2 Answers2

Linked