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;
}
The original code is lacking following declarations to compile :
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
, nextrightop
and finallyleftop
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 befor (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 lastpost
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 thefor
.With all those fixes, the code could be :
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 ;-)
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 righte.g.
for ab+c* you want
and then evaluate the tree either recursively or not. everytime the operator is + or - use parenthesis around it,