infix to postfix

I have written a program to convert from infix to postfix
but it is not working properly....


#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
int presidence();
int infixToPostfix(char *);
template<class T>
class Stack
{
private:
T *data;
int capacity;
int top;

public:
Stack();
Stack(int );
T pop();
void push(T);
int isEmpty();
int isFull();
int getTop();
~Stack();
};


void main()
{
clrscr();
char arr[10]="A+B/C*E";
int a=infixToPostfix(arr);
cout<<a;
getch();
}

template<class T>
Stack<T> ::Stack()
{
capacity=0;
top=0;
}
template<class T>
Stack<T>::Stack(int s=5)
{
capacity=s;
data=new T[capacity];
top=0;
}
template<class T>
void Stack<T>:: push(T p)
{
if(isFull())
{
return;
}
else
{
data[top]=p;
top++;
}
}
template<class T>
T Stack<T>:: pop()
{
if(isEmpty())
exit(0);
else
{
top--;
return data[top];
}
}
template<class T>
int Stack<T>:: isEmpty()
{
return (top==0);
}
template<class T>
int Stack <T>:: isFull()
{
return (top==capacity);
}

template<class T>
Stack<T>::~Stack()
{
if(data!=NULL)
{
delete[] data;
data=0;
}
}
template<class T>
int Stack<T>::getTop()
{
return top;
}
int presidence(char A,char B)
{
if(A=='+' && B=='+' ||A=='-' && B=='-'||A=='*' && B=='*'||A=='/' && B=='/')
{
return A;
}
else if(A=='+' && B=='-' ||A=='-' && B=='+'||A=='*' && B=='/' ||A=='/' && B=='*')
{
return A;
}
else if(A=='+' && B=='*' ||A=='-' && B=='*'||A=='+' && B=='/' ||A=='-' && B=='/')
{
return B;
}
else
return 0;
}

int infixToPostfix(char *S)
{
int len=strlen(S);
char *S1;
S1=new char[10];
int temp;
Stack <char> P(len+1);

for(int i=0;i<len;i++)
{
if(S[i]>='A'&&S[i]<='Z'||S[i]>='a'&&S[i]<='z')
{
S1[i]=S[i];
}
else if(S[i]=='+' ||S[i]=='-' ||S[i]=='*' ||S[i]=='/')
{
if(P.isEmpty())
{
P.push(S[i]);
}
else
{
// while(!P.isEmpty())
{
temp=presidence(S[i],S[P.getTop()]);
S1[i]=temp;
}
P.push(S[i]);
}
cout<<S[i];
}
}
return -1;
}
can any one help me regarding this problem....
thanx in advance
i have added some functions but they are not working properly...
1. your precidence function is not returning correct values.
2. you cannot use i for S1[i] in S1[i] = S[i] because S1 only will contains operands so when an operator comes i will increment which will corrupt S1. check this out.
it shouldbe something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
for(int i=0, j = 0;i<len;i++)
	{
		if(S[i]>='A'&&S[i]<='Z'||S[i]>='a'&&S[i]<='z')
		{
			S1[j]=S[i];
			j++;
		}
		else if(S[i]=='+' ||S[i]=='-' ||S[i]=='*' ||S[i]=='/')
		{
			if(P.isEmpty())
			{
				P.push(S[i]);
			}
			else
			{
				// while(!P.isEmpty())
				{
				temp=presidence(S[i],S[P.getTop()]);
				S1[i]=temp;
				}
				P.push(S[i]);
			}
			cout<<S[i];

		}

	}


though its not perfect..but you can explore this thing a little.
I cant understand how to make precidence function
the function which i have made is


int presidence(char A,char B)
{
if(A=='+' && B=='-' || A=='*' && B=='/')
{
return 1;
}

if(A=='-' && B=='+' || A=='/' && B=='*')
return 1;

if(A=='+' && B=='*' || B=='-'||A=='/' && B=='+' ||A=='/' && B=='-')
{
return 1;
}
if(A=='*' && B=='+' || A=='*' && B=='-')
return 0;
return 0;
}

but it is not working properly.......
plz help me out........
thanx 4 pointing error I have corrected this error....
see you are trying correctly, but this way your precidence function will have many comparisons.. think something dirrerent. think of a generalized rule. will try this function and post it soon.

whenever you post code put it in code blocks (#).
Last edited on
what do u mean by generalized code....??
generalized means so that you dont have to put so many conditions...

have a look at this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int presidence(char curr_op, char op_stack) //current_operator vs operator_stack
{
if(ip(curr_op) >= isp(op_stack))   //i've written two functions input priority and instack priority
return curr_op;
else
return op_stack;
}

int ip(char x)
{
	switch(x)
	{
	case '+':
	case '-':
		return 1;
		
	case '*':
	case '/':
		return 2;

	case '^':
		return 4;
	}
	return 0;
}

int isp(char x)
{
	switch(x)
	{
	case '+':
	case '-':
		return 1;
		
	case '*':
	case '/':
		return 2;
	case '^':
		return 3;
	}
	return 0;
}


see if this code works.. you can try something like this. and then see if your code starts to work fine. :)
thanx alot......:)
is the code working fine now??
garbage values are handled but i cant get correct solution.....:(

I m still trying to correct it......
now the code is
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>

int presidence(char ,char );
void infixToPostfix(char *);
int ip(char );
int isp(char );
template<class T>
class Stack
{
	private:
   	T *data;
      int capacity;
      int top;

   public:
   	Stack();
      Stack(int );
      T pop();
      void push(T);
      int isEmpty();
      int isFull();
      T stackTop();
	  ~Stack();
	  void display()
	  {
		for(int i = 0 ; i < top ; i++)
			cout<<"  " <<data[i];
	  }
};


void main()
{
   clrscr();
   char arr[] = "A+B*(C+D-E/F*G)";
   infixToPostfix(arr);
   getch();
}

template<class T>
Stack<T> ::Stack()
{
	capacity=0;
	top=0;
}
template<class T>
Stack<T>::Stack(int s=5)
{
	capacity=s;
	data=new T[capacity];
	top=0;
}
template<class T>
int Stack<T>:: isEmpty()
{
	return (top==0);
}
template<class T>
int Stack <T>:: isFull()
{
	return (top==capacity);
}
template<class T>
void Stack<T>:: push(T p)
{
	if(isFull())
	{
		return;
	}
	else
	{
		data[top]=p;
  		top++;
	}
}
template<class T>
T Stack<T>:: pop()
{
  /*	if(isEmpty())
  		exit(0);
 	else
  	{*/
     	top--;
		return data[top];
  // }
}
template<class T>
Stack<T>::~Stack()
{
	if(data!=NULL)
	{
		delete[] data;
  		data=0;
	}
}
template<class T>
T Stack<T>::stackTop()
{
	return data[top-1];
}
int ip(char x)
{
	switch(x)
	{
	case '+':
	case '-':
		return 1;

	case '*':
	case '/':
		return 2;

	case '^':
		return 4;
	}
	return 0;
}

int isp(char x)
{
	switch(x)
	{
	case '+':
	case '-':
		return 1;

	case '*':
	case '/':
		return 2;
	case '^':
		return 3;
	}
	return 0;
}

int presidence(char curr_op, char op_stack) //current_operator vs operator_stack
{
	if(ip(curr_op) >= isp(op_stack))   //i've written two functions input priority and instack priority
		return curr_op;
	else
		return op_stack;
}

void infixToPostfix(char *infix)
{
	int len=strlen(infix);
	char postfix[20];
	Stack <char> P(len+1);
   int pi = 0;

   for(int i=0;infix[i]!='\0';i++)
   {
		if(infix[i]>='A' && infix[i]<='Z')
	  {
			postfix[pi]=infix[i];
			pi++;
	  }
	  if(infix[i]=='+' ||infix[i]=='-'||infix[i]=='*'||infix[i]=='/')
	  {
			if(P.isEmpty() || infix[i-1]=='(')
			{
				P.push(infix[i]);
			}
			else if(!P.isEmpty() || infix[i-1]!='(')
			{
			 	while(!P.isEmpty() && (presidence(infix[i],P.stackTop())))
				{
					postfix[pi]=P.pop();
               pi++;
				}
				P.push(infix[i]);
				if(infix[i]!=')')
				{
					P.push(infix[i]);
				}
				else if(infix[i]==')')
				{
				  	while(P.pop()!='(')
		  			{
						postfix[pi]=P.pop();
						pi++;
	 		   	}

				}
			}

	  }
   }
   for(int i=pi;!P.isEmpty() && i<=len;i++)
   {
		postfix[i]=P.pop();
   }
   for(int j=0;j<=pi;j++)
		cout<<" "<<postfix[j];
}
the postfix string is not correct........

plz check it whether i m doing right or not..
this is not correct. which platform you are working on??
i think you never debug your program.. the code which i send you, you are using it incorrectly.
when you send it A or B it returns you either A or B whose prec is higher. but in your code you are using it like this:

while(!P.isEmpty() && (presidence(infix[i],P.stackTop())))
you are not saving the return value of presidence, how will you know what the function is returning..

my first suggestion is dont use '(' and ')'. first make your minimum program working and then give it more features. ok? starting with a complex program is not good idea.
so remove this feature from your first working version if you like this advise.
now what you have to do is:
modify the return type of presidence function to bool, now it will be like this:
if(presidence(a, b)) this will return true if a is greater presidence else false.

then what you can do is:
1
2
3
4
5
6
7
8
9
10
if(presidence(input, instack))
{
//input has greater presidence so put input operator in the postfix array
}
else
{
//input has less presidence
//pop the operator stack, put the popped character in the postfix array
//and put the input operator in the operator stack. correct?
}


give it a try then i will help you. i hope you are getting what i mean??
just make a small program, dont try too many features with it or you will be drowned in the complexity.
:)
thanx 4 ur help.....

I have corrected my program according to ur instructions.....


and now it is working properly....:)
great..!! :)
Topic archived. No new replies allowed.