infix to postfix conversion c 2b 2b

1/*https://github.com/Sudhanshu1304/Stack-Application*/
2
3#include <iostream>
4#include<string>
5using namespace std;
6
7
8
9class Stack{
10
11
12private:
13
14
15    char A[5];
16    int Size;
17
18public:
19    int top;
20    Stack(){
21
22        top=-1;
23        Size=sizeof(A)/sizeof(char);
24
25    }
26
27
28
29    bool IsFull(){
30
31        if(top==Size-1){
32            return true;
33        }
34        else{
35            return false;
36        }
37    }
38
39    bool IsEmpty(){
40
41        if(top==-1){
42            return true;
43        }
44        else{
45            return false;
46        }
47    }
48
49    char peek(){
50
51        return A[top];
52    }
53
54    void Push(char val){
55
56        if (IsFull()==false){
57            top++;
58            A[top]=val;
59        }
60        else{
61            cout<<"\nThe Stack is Full"<<endl;
62        }
63    }
64
65    char Pop(){
66
67        if(IsEmpty()==false){
68            char temp=A[top];
69            A[top]='0';
70            top--;
71            return temp;
72        }
73        else{
74            return '-1';
75        }
76
77    }
78
79    void Show_Stack(){
80
81
82        for(int i=0;i<top+1;i++){
83            cout<<A[i];
84        }
85
86
87    }
88
89};
90
91
92int Search(char A){
93
94
95    string CHAR[]={"([","{)","]}","+-","*/","^$"};
96    int Size=(sizeof(CHAR)/sizeof(string));
97
98    for(int i=0;i<Size;i++){
99
100        if(A==CHAR[i][0]){
101                if(i+i>=6){
102                    return i+i;
103                }
104                else{
105                    return i+i+0;
106                }
107
108        }
109        else if(CHAR[i][1]==A){
110             if(i+i>=6){
111                    return i+i;
112                }
113                else{
114                    return i+i+1;
115                }
116        }
117    }
118    return -1;
119
120}
121
122
123
124
125void Display(char ch,string vari, Stack &s){
126
127    int Size=s.top+1;
128
129
130    cout<<"\n   "<<ch<<"           ";
131    s.Show_Stack();
132    for(int i=0;i<10-Size;i++){
133        cout<<" ";
134    }
135    cout<<vari<<endl;
136
137}
138
139
140int main(){
141
142    Stack STACK;
143    char temp;
144    string exp;//"A+B*C";
145    cout<<"Enter Your Expression :";
146    cin>>exp;
147
148    string out="";
149    cout<<"\n\nExpression   Stack   Postfix\n"<<endl;
150    for(int i=0;i<exp.size();i++){
151
152        temp=exp[i];
153
154        int ab=Search(temp);
155
156        if (ab!=-1){
157
158            /* If We ENCOUNTER CLOSING BRACKETS*/
159            if(ab<=5 && ab>=3){
160
161
162
163                while(Search(STACK.peek())>2){
164                    char val=STACK.Pop();
165                        out=out+val;
166
167                    Display(temp,out,STACK);
168                }
169                STACK.Pop();
170                Display(temp,out,STACK);
171                }
172            /* Search Precedence*/
173            else{
174                if (Search(temp)>=0 && Search(temp)<=2){
175                    STACK.Push(temp);
176                    Display(temp,out,STACK);
177                }
178
179                /* If TOP < Temp */
180
181                else if(Search(STACK.peek())<ab){
182
183                        STACK.Push(temp);
184                        Display(temp,out,STACK);
185                }
186                else{
187                    /* if STACK= +,* and temp= + then we have to remove two times */
188
189
190                    while(Search(STACK.peek())>=ab){
191
192                        char val=STACK.Pop();
193                            out=out+val;
194                        Display(temp,out,STACK);
195                    }
196                    STACK.Push(temp);
197                    Display(temp,out,STACK);
198                }
199            }
200        }
201        /* If an Alphabet */
202        else{
203
204            out=out+temp;
205            Display(temp,out,STACK);
206
207            }
208
209
210    }
211    while(STACK.IsEmpty()==false){
212
213        char val=STACK.Pop();
214
215            out=out+val;
216        Display(temp,out,STACK);
217
218    }
219    cout<<"\n\nFINAL STRING : "<<out<<endl;
220
221
222}

1Best Solution
2-------------------------------------------------------------------
3#include<bits/stdc++.h>
4using namespace std;
5
6int prec(char c) {
7    if(c == '^') {
8        return 3;
9    }
10    else if(c == '*' || c == '/') {
11        return 2;
12    }
13    else if(c == '+' || c =='-') {
14        return 1;
15    }
16    else {
17        return -1;
18    }
19}
20
21string infixToPostfix(string s) {
22    stack<char> st;
23    string res;
24
25    for (int i = 0; i < s.length(); i++)
26    {
27        if((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z')) {
28            res += s[i];
29        }
30        else if(s[i] == '(') {
31            st.push(s[i]);
32        }
33        else if(s[i] == ')') {
34            while (!st.empty() && st.top() != '(')
35            {
36                res += st.top();
37                st.pop();
38            }
39            if(!st.empty()) {
40                st.pop(); // Popping '(' here
41            }
42        }
43        else {
44            while (!st.empty() && prec(st.top()) >= prec(s[i]))
45            {
46                res += st.top();
47                st.pop();
48            }
49            st.push(s[i]);
50        }
51    }
52    
53    while (!st.empty())
54    {
55       res += st.top();
56       st.pop();
57    }
58    
59    return res;
60}
61
62int main() {
63    string exp = "a+b*(c^d-e)^(f+g*h)-i";
64    cout<<infixToPostfix(exp);
65    return 0;
66}

1//Easiet way to solve infix to postfix expression
2bool isOperator(char c)
3{
4	if(c=='+'||c=='-'||c=='*'||c=='/'||c=='^')
5	{
6		return true;
7	}
8	else
9	{
10		return false;
11	}
12}
13
14int precedence(char c) 
15{ 
16    if(c == '^') 
17    return 3; 
18    else if(c == '*' || c == '/') 
19    return 2; 
20    else if(c == '+' || c == '-') 
21    return 1; 
22    else
23    return -1; 
24} 
25
26string InfixToPostfix(stack<char> s, string infix)
27{
28	string postfix;
29	for(int i=0;i<infix.length();i++)
30	{
31		if((infix[i] >= 'a' && infix[i] <= 'z')
32		||(infix[i] >= 'A' && infix[i] <= 'Z'))
33		{
34			postfix+=infix[i];
35		}
36		else if(infix[i] == '(')
37		{
38			s.push(infix[i]);
39		}
40		else if(infix[i] == ')')
41		{
42			while((s.top()!='(') && (!s.empty()))
43			{
44				char temp=s.top();
45				postfix+=temp;
46				s.pop();
47			}
48			if(s.top()=='(')
49			{
50				s.pop();
51			}
52		}
53		else if(isOperator(infix[i]))
54		{
55			if(s.empty())
56			{
57				s.push(infix[i]);
58			}
59			else
60			{
61				if(precedence(infix[i])>precedence(s.top()))
62				{
63					s.push(infix[i]);
64				}	
65				else if((precedence(infix[i])==precedence(s.top()))&&(infix[i]=='^'))
66				{
67					s.push(infix[i]);
68				}
69				else
70				{
71					while((!s.empty())&&( precedence(infix[i])<=precedence(s.top())))
72					{
73						postfix+=s.top();
74						s.pop();
75					}
76					s.push(infix[i]);
77				}
78			}
79		}
80	}
81	while(!s.empty())
82	{
83		postfix+=s.top();
84		s.pop();
85	}
86	
87	return postfix;
88}
89
90int main() 
91{  
92
93  	string infix_exp, postfix_exp;
94  	cout<<"Enter a Infix Expression :"<<endl;
95  	cin>>infix_exp;
96  	stack <char> stack;
97	cout<<"INFIX EXPRESSION: "<<infix_exp<<endl;
98  	postfix_exp = InfixToPostfix(stack, infix_exp);
99  	cout<<endl<<"POSTFIX EXPRESSION: "<<postfix_exp;
100	  
101	return 0;
102}

1Begin
2   initially push some special character say # into the stack
3   for each character ch from infix expression, do
4      if ch is alphanumeric character, then
5         add ch to postfix expression
6      else if ch = opening parenthesis (, then
7         push ( into stack
8      else if ch = ^, then            //exponential operator of higher precedence
9         push ^ into the stack
10      else if ch = closing parenthesis ), then
11         while stack is not empty and stack top ≠ (,
12            do pop and add item from stack to postfix expression
13         done
14
15         pop ( also from the stack
16      else
17         while stack is not empty AND precedence of ch <= precedence of stack top element, do
18            pop and add into postfix expression
19         done
20
21         push the newly coming character.
22   done
23
24   while the stack contains some remaining characters, do
25      pop and add to the postfix expression
26   done
27   return postfix
28End