Register to reply

C++: Postfix to Infix

by DefaultName
Tags: infix, postfix
Share this thread:
DefaultName
#1
Mar7-07, 09:03 PM
P: 181
1. The problem statement, all variables and given/known data

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

2. Relevant equations

None.

3. 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?
Phys.Org News Partner Science news on Phys.org
Experts defend operational earthquake forecasting, counter critiques
EU urged to convert TV frequencies to mobile broadband
Sierra Nevada freshwater runoff could drop 26 percent by 2100
learingToCode
#2
Mar6-10, 02:47 PM
P: 1
#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*$*+

Quote Quote by DefaultName View Post
1. The problem statement, all variables and given/known data

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

2. Relevant equations

None.

3. 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?


Register to reply

Related Discussions
C++: Postfix to Infix Programming & Computer Science 0