-
Notifications
You must be signed in to change notification settings - Fork 1
/
InfixToPostfix.rtf
172 lines (171 loc) · 6.33 KB
/
InfixToPostfix.rtf
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
{\rtf1\ansi\ansicpg1252\cocoartf1265\cocoasubrtf210
{\fonttbl\f0\fnil\fcharset0 Consolas;}
{\colortbl;\red255\green255\blue255;\red132\green134\blue132;\red255\green255\blue255;\red38\green38\blue38;
\red148\green6\blue75;\red213\green58\blue6;\red101\green71\blue146;\red14\green114\blue164;}
\paperw11900\paperh16840\margl1440\margr1440\vieww10800\viewh8400\viewkind0
\deftab720
\pard\pardeftab720\sl320
\f0\fs24 \cf2 \cb3 /*\cf4 \
\cf2 Infix to postfix conversion in C++ \cf4 \
\cf2 Input Postfix expression must be in a desired format. \cf4 \
\cf2 Operands and operator, both must be single character.\cf4 \
\cf2 Only '+' , '-' , '*', '/' and '$' (for exponentiation) operators are expected. \cf4 \
\cf2 */\cf4 \
#\cf5 include\cf6 <iostream>\cf4 \
#\cf5 include\cf6 <stack>\cf4 \
#\cf5 include\cf6 <string>\cf4 \
\'a0\
\pard\pardeftab720\sl320
\cf5 using\cf4 \cf5 namespace\cf4 \cf7 std\cf5 ;\cf4 \
\'a0\
\pard\pardeftab720\sl320
\cf2 // Function to convert Infix expression to postfix \cf4 \
string \cf7 InfixToPostfix\cf4 (string expression);\
\'a0\
\cf2 // Function to verify whether an operator has higher precedence over other\cf4 \
\pard\pardeftab720\sl320
\cf5 int\cf4 \cf7 HasHigherPrecedence\cf4 (\cf5 char\cf4 operator1, \cf5 char\cf4 operator2);\
\'a0\
\pard\pardeftab720\sl320
\cf2 // Function to verify whether a character is operator symbol or not. \cf4 \
\pard\pardeftab720\sl320
\cf5 bool\cf4 \cf7 IsOperator\cf4 (\cf5 char\cf4 C);\
\'a0\
\pard\pardeftab720\sl320
\cf2 // Function to verify whether a character is alphanumeric chanaracter (letter or numeric digit) or not. \cf4 \
\pard\pardeftab720\sl320
\cf5 bool\cf4 \cf7 IsOperand\cf4 (\cf5 char\cf4 C);\
\'a0\
\cf5 int\cf4 \cf7 main\cf4 () \
\{\
string expression; \
cout<<\cf6 "Enter Infix Expression \\n"\cf4 ;\
\cf8 getline\cf4 (cin,expression);\
string postfix = \cf8 InfixToPostfix\cf4 (expression);\
cout<<\cf6 "Output = "\cf4 <<postfix<<\cf6 "\\n"\cf4 ;\
\}\
\'a0\
\pard\pardeftab720\sl320
\cf2 // Function to evaluate Postfix expression and return output\cf4 \
string \cf7 InfixToPostfix\cf4 (string expression)\
\{\
\cf2 // Declaring a Stack from Standard template library in C++. \cf4 \
stack<\cf5 char\cf4 > S;\
string postfix = \cf6 ""\cf4 ; \cf2 // Initialize postfix as empty string.\cf4 \
\cf5 for\cf4 (\cf5 int\cf4 i = \cf8 0\cf4 ;i< expression.\cf8 length\cf4 ();i++) \{\
\'a0\
\cf2 // Scanning each character from left. \cf4 \
\cf2 // If character is a delimitter, move on. \cf4 \
\cf5 if\cf4 (expression[i] == \cf6 ' '\cf4 || expression[i] == \cf6 ','\cf4 ) \cf5 continue\cf4 ; \
\'a0\
\cf2 // If character is operator, pop two elements from stack, perform operation and push the result back. \cf4 \
\cf5 else\cf4 \cf5 if\cf4 (\cf8 IsOperator\cf4 (expression[i])) \
\{\
\cf5 while\cf4 (!S.\cf8 empty\cf4 () && S.\cf8 top\cf4 () != \cf6 '('\cf4 && \cf8 HasHigherPrecedence\cf4 (S.\cf8 top\cf4 (),expression[i]))\
\{\
postfix+= S.\cf8 top\cf4 ();\
S.\cf8 pop\cf4 ();\
\}\
S.\cf8 push\cf4 (expression[i]);\
\}\
\cf2 // Else if character is an operand\cf4 \
\cf5 else\cf4 \cf5 if\cf4 (\cf8 IsOperand\cf4 (expression[i]))\
\{\
postfix +=expression[i];\
\}\
\'a0\
\cf5 else\cf4 \cf5 if\cf4 (expression[i] == \cf6 '('\cf4 ) \
\{\
S.\cf8 push\cf4 (expression[i]);\
\}\
\'a0\
\cf5 else\cf4 \cf5 if\cf4 (expression[i] == \cf6 ')'\cf4 ) \
\{\
\cf5 while\cf4 (!S.\cf8 empty\cf4 () && S.\cf8 top\cf4 () != \cf6 '('\cf4 ) \{\
postfix += S.\cf8 top\cf4 ();\
S.\cf8 pop\cf4 ();\
\}\
S.\cf8 pop\cf4 ();\
\}\
\}\
\'a0\
\cf5 while\cf4 (!S.\cf8 empty\cf4 ()) \{\
postfix += S.\cf8 top\cf4 ();\
S.\cf8 pop\cf4 ();\
\}\
\'a0\
\cf5 return\cf4 postfix;\
\}\
\'a0\
\cf2 // Function to verify whether a character is english letter or numeric digit. \cf4 \
\cf2 // We are assuming in this solution that operand will be a single character\cf4 \
\pard\pardeftab720\sl320
\cf5 bool\cf4 \cf7 IsOperand\cf4 (\cf5 char\cf4 C) \
\{\
\cf5 if\cf4 (C >= \cf6 '0'\cf4 && C <= \cf6 '9'\cf4 ) \cf5 return\cf4 \cf8 true\cf4 ;\
\cf5 if\cf4 (C >= \cf6 'a'\cf4 && C <= \cf6 'z'\cf4 ) \cf5 return\cf4 \cf8 true\cf4 ;\
\cf5 if\cf4 (C >= \cf6 'A'\cf4 && C <= \cf6 'Z'\cf4 ) \cf5 return\cf4 \cf8 true\cf4 ;\
\cf5 return\cf4 \cf8 false\cf4 ;\
\}\
\'a0\
\pard\pardeftab720\sl320
\cf2 // Function to verify whether a character is operator symbol or not. \cf4 \
\pard\pardeftab720\sl320
\cf5 bool\cf4 \cf7 IsOperator\cf4 (\cf5 char\cf4 C)\
\{\
\cf5 if\cf4 (C == \cf6 '+'\cf4 || C == \cf6 '-'\cf4 || C == \cf6 '*'\cf4 || C == \cf6 '/'\cf4 || C== \cf6 '$'\cf4 )\
\cf5 return\cf4 \cf8 true\cf4 ;\
\'a0\
\cf5 return\cf4 \cf8 false\cf4 ;\
\}\
\'a0\
\pard\pardeftab720\sl320
\cf2 // Function to verify whether an operator is right associative or not. \cf4 \
\pard\pardeftab720\sl320
\cf5 int\cf4 \cf7 IsRightAssociative\cf4 (\cf5 char\cf4 op)\
\{\
\cf5 if\cf4 (op == \cf6 '$'\cf4 ) \cf5 return\cf4 \cf8 true\cf4 ;\
\cf5 return\cf4 \cf8 false\cf4 ;\
\}\
\'a0\
\pard\pardeftab720\sl320
\cf2 // Function to get weight of an operator. An operator with higher weight will have higher precedence. \cf4 \
\pard\pardeftab720\sl320
\cf5 int\cf4 \cf7 GetOperatorWeight\cf4 (\cf5 char\cf4 op)\
\{\
\cf5 int\cf4 weight = -\cf8 1\cf4 ; \
\cf5 switch\cf4 (op)\
\{\
\cf5 case\cf4 \cf6 '+'\cf4 :\
\cf5 case\cf4 \cf6 '-'\cf4 :\
weight = \cf8 1\cf4 ;\
break;\
\cf5 case\cf4 \cf6 '*'\cf4 :\
\cf5 case\cf4 \cf6 '/'\cf4 :\
weight = \cf8 2\cf4 ;\
break;\
\cf5 case\cf4 \cf6 '$'\cf4 :\
weight = \cf8 3\cf4 ;\
\}\
\cf5 return\cf4 weight;\
\}\
\'a0\
\pard\pardeftab720\sl320
\cf2 // Function to perform an operation and return output. \cf4 \
\pard\pardeftab720\sl320
\cf5 int\cf4 \cf7 HasHigherPrecedence\cf4 (\cf5 char\cf4 op1, \cf5 char\cf4 op2)\
\{\
\cf5 int\cf4 op1Weight = \cf8 GetOperatorWeight\cf4 (op1);\
\cf5 int\cf4 op2Weight = \cf8 GetOperatorWeight\cf4 (op2);\
\'a0\
\cf2 // If operators have equal precedence, return true if they are left associative. \cf4 \
\cf2 // return false, if right associative. \cf4 \
\cf2 // if operator is left-associative, left one should be given priority. \cf4 \
\cf5 if\cf4 (op1Weight == op2Weight)\
\{\
\cf5 if\cf4 (\cf8 IsRightAssociative\cf4 (op1)) \cf5 return\cf4 \cf8 false\cf4 ;\
\cf5 else\cf4 \cf5 return\cf4 \cf8 true\cf4 ;\
\}\
\cf5 return\cf4 op1Weight > op2Weight ? \cf8 true\cf4 : \cf8 false\cf4 ;\
\}\
}