Comp Sci C++: Postfix to Infix Conversion - Homework Solution

[DefaultName]

Homework Statement

Convert a postfix expression to the corresponding fully parenthesized infix expression...

Homework Equations

None.

The Attempt at a Solution

#include<iostream>
#include<cctype>
#include<string>

#include "MyStack.h"
#include "MyStack.cpp"

using namespace std;

void displayGreeting();

int main()
{
	MyStack s1, temp;
	string postfix, infix, tempstr;
	char token;
	
	displayGreeting();

	cout << "Postfix expression: ";
	getline(cin, postfix);	
	cout << "You entered: " << postfix << endl;

	for (int i = 0; i < postfix.length(); i++)
	{
		token = postfix[i];
		if (!isspace(token))
		 if(isdigit(token) || isalpha(token))
			s1.push(token);			
		 else if(token == '+' || '-' || '*' || '/')
			temp.push(token);
	}
	
	s1.display(cout);
	temp.display(cout);	
	
	return 0;	
};

This is the code I have so far. I have two stacks

1) Stack s1, where it holds the digits or variables... such as a, b, 3...
2) Stack temp, where it holds the operands

I have a MyStack class, which is fine. I just need help developing an algorithm of converting something like this:

abc+* to (a*(b+c))... Any tips?

 

[learingToCode]

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

bool prcd(char op1, char op2) {
		if(op1 == '+' && op2 == '*')
			return false;
		else if(op1 == '*' && op2 == '+')
			return true;
		else if(op1 == '-' && op2 == '*')
			return false;
		else if(op1 == '*' && op2 == '-')
			return true;
		else if(op1 == '$' && op2 == '*')
			return true;
		else if(op1 == '*' && op2 == '$')
			return false;
		else if(op1 == '$' && op2 == '+')
			return true;
		else if(op1 == '$' && op2 == '-')
			return true;
		
		return false;

	}
std::string postToIn(std::string post) {
		
		std::string tmp = "";
		std::string infix = "";
		typedef struct Operand {
			std::string str;
			char oper;
		}Operand;
		typedef stack<Operand> OpndStk;
		OpndStk os;
		for(int i=0; i<post.size(); i++)
		{
			Operand o;
			if(isalpha(post[i]))
			{
				o.str = "";
				o.str += post[i];
				o.oper = ' ';
				os.push(o);
				continue;
			}
			else
			{
				Operand op2 = os.top();
				os.pop();
				Operand op1 = os.top();
				os.pop();
				if( op2.oper != ' ')
				{
					if(prcd(post[i],op2.oper))
					{
						op2.str.insert(0,"(");
						op2.str.append(")");
					}
				}
				if( op1.oper != ' ')
				{
					if(prcd(post[i],op1.oper))
					{
						op1.str.insert(0,"(");
						op1.str.append(")");
					}
				}
				tmp = op1.str+post[i]+op2.str;
				Operand t;
				t.str = tmp;
				t.oper = post[i];
				os.push(t);
				
			}
		}
		infix = os.top().str;
		os.pop();
		return infix;
	}

I have used extra info in each operand pushed on the stack to produce an infix which uses minimal parantheses(i.e uses only which are necessary). Idea is whenever u apply an operator, check whether any of its operands is itself result of applying any operator and, if yes, check whether the precedence of the most recent operator is higher than the operator applied to that operand and, if yes, u need parantheses around the operand. This is so because operators are applied in the order that they appear in postfix notation and while converting to infix, if an operator appearing earlier has lower precedence than the one appearing later then we need parantheses around the infix notation of the earlier operator.

I think the above para is very confusing... Sorry about that but i have been trying this for the last 12 hrs and my head is spinning too.
i tested this with the following postfix strings:
--> ABC*+
--> AB+C*
-->ABC-DEF*$*+

Homework Statement

Convert a postfix expression to the corresponding fully parenthesized infix expression...

Homework Equations

None.

The Attempt at a Solution

#include<iostream>
#include<cctype>
#include<string>

#include "MyStack.h"
#include "MyStack.cpp"

using namespace std;

void displayGreeting();

int main()
{
	MyStack s1, temp;
	string postfix, infix, tempstr;
	char token;
	
	displayGreeting();

	cout << "Postfix expression: ";
	getline(cin, postfix);	
	cout << "You entered: " << postfix << endl;

	for (int i = 0; i < postfix.length(); i++)
	{
		token = postfix[i];
		if (!isspace(token))
		 if(isdigit(token) || isalpha(token))
			s1.push(token);			
		 else if(token == '+' || '-' || '*' || '/')
			temp.push(token);
	}
	
	s1.display(cout);
	temp.display(cout);	
	
	return 0;	
};

This is the code I have so far. I have two stacks

1) Stack s1, where it holds the digits or variables... such as a, b, 3...
2) Stack temp, where it holds the operands

I have a MyStack class, which is fine. I just need help developing an algorithm of converting something like this:

abc+* to (a*(b+c))... Any tips?