-
Notifications
You must be signed in to change notification settings - Fork 1
/
PostfixEvaluation.rtf
134 lines (132 loc) · 5.99 KB
/
PostfixEvaluation.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
{\rtf1\ansi\ansicpg1252\cocoartf1265\cocoasubrtf210
{\fonttbl\f0\fswiss\fcharset0 Helvetica;\f1\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
\pard\tx566\tx1133\tx1700\tx2267\tx2834\tx3401\tx3968\tx4535\tx5102\tx5669\tx6236\tx6803\pardirnatural
\f0\fs24 \cf0 //{\field{\*\fldinst{HYPERLINK "https://gist.github.com/mycodeschool/7702441"}}{\fldrslt https://gist.github.com/mycodeschool/7702441}}\
\pard\pardeftab720\sl320
\f1 \cf2 \cb3 /*\cf4 \
\cf2 Evaluation Of postfix Expression in C++ \cf4 \
\cf2 Input Postfix expression must be in a desired format. \cf4 \
\cf2 Operands must be integers and there should be space in between two operands.\cf4 \
\cf2 Only '+' , '-' , '*' and '/' 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 evaluate Postfix expression and return output\cf4 \
\pard\pardeftab720\sl320
\cf5 int\cf4 \cf7 EvaluatePostfix\cf4 (string expression);\
\'a0\
\pard\pardeftab720\sl320
\cf2 // Function to perform an operation and return output. \cf4 \
\pard\pardeftab720\sl320
\cf5 int\cf4 \cf7 PerformOperation\cf4 (\cf5 char\cf4 operation, \cf5 int\cf4 operand1, \cf5 int\cf4 operand2);\
\'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 numeric digit. \cf4 \
\pard\pardeftab720\sl320
\cf5 bool\cf4 \cf7 IsNumericDigit\cf4 (\cf5 char\cf4 C);\
\'a0\
\cf5 int\cf4 \cf7 main\cf4 () \
\{\
string expression; \
cout<<\cf6 "Enter Postfix Expression \\n"\cf4 ;\
\cf8 getline\cf4 (cin,expression);\
\cf5 int\cf4 result = \cf8 EvaluatePostfix\cf4 (expression);\
cout<<\cf6 "Output = "\cf4 <<result<<\cf6 "\\n"\cf4 ;\
\}\
\'a0\
\pard\pardeftab720\sl320
\cf2 // Function to evaluate Postfix expression and return output\cf4 \
\pard\pardeftab720\sl320
\cf5 int\cf4 \cf7 EvaluatePostfix\cf4 (string expression)\
\{\
\cf2 // Declaring a Stack from Standard template library in C++. \cf4 \
stack<\cf5 int\cf4 > S;\
\'a0\
\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])) \{\
\cf2 // Pop two operands. \cf4 \
\cf5 int\cf4 operand2 = S.\cf8 top\cf4 (); S.\cf8 pop\cf4 ();\
\cf5 int\cf4 operand1 = S.\cf8 top\cf4 (); S.\cf8 pop\cf4 ();\
\cf2 // Perform operation\cf4 \
\cf5 int\cf4 result = \cf8 PerformOperation\cf4 (expression[i], operand1, operand2);\
\cf2 //Push back result of operation on stack. \cf4 \
S.\cf8 push\cf4 (result);\
\}\
\cf5 else\cf4 \cf5 if\cf4 (\cf8 IsNumericDigit\cf4 (expression[i]))\{\
\cf2 // Extract the numeric operand from the string\cf4 \
\cf2 // Keep incrementing i as long as you are getting a numeric digit. \cf4 \
\cf5 int\cf4 operand = \cf8 0\cf4 ; \
\cf5 while\cf4 (i<expression.\cf8 length\cf4 () && \cf8 IsNumericDigit\cf4 (expression[i])) \{\
\cf2 // For a number with more than one digits, as we are scanning from left to right. \cf4 \
\cf2 // Everytime , we get a digit towards right, we can multiply current total in operand by 10 \cf4 \
\cf2 // and add the new digit. \cf4 \
operand = (operand*\cf8 10\cf4 ) + (expression[i] - \cf6 '0'\cf4 ); \
i++;\
\}\
\cf2 // Finally, you will come out of while loop with i set to a non-numeric character or end of string\cf4 \
\cf2 // decrement i because it will be incremented in increment section of loop once again. \cf4 \
\cf2 // We do not want to skip the non-numeric character by incrementing i twice. \cf4 \
i--;\
\'a0\
\cf2 // Push operand on stack. \cf4 \
S.\cf8 push\cf4 (operand);\
\}\
\}\
\cf2 // If expression is in correct format, Stack will finally have one element. This will be the output. \cf4 \
\cf5 return\cf4 S.\cf8 top\cf4 ();\
\}\
\'a0\
\pard\pardeftab720\sl320
\cf2 // Function to verify whether a character is numeric digit. \cf4 \
\pard\pardeftab720\sl320
\cf5 bool\cf4 \cf7 IsNumericDigit\cf4 (\cf5 char\cf4 C) \
\{\
\cf5 if\cf4 (C >= \cf6 '0'\cf4 && C <= \cf6 '9'\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 )\
\cf5 return\cf4 \cf8 true\cf4 ;\
\'a0\
\cf5 return\cf4 \cf8 false\cf4 ;\
\}\
\'a0\
\pard\pardeftab720\sl320
\cf2 // Function to perform an operation and return output. \cf4 \
\pard\pardeftab720\sl320
\cf5 int\cf4 \cf7 PerformOperation\cf4 (\cf5 char\cf4 operation, \cf5 int\cf4 operand1, \cf5 int\cf4 operand2)\
\{\
\cf5 if\cf4 (operation == \cf6 '+'\cf4 ) \cf5 return\cf4 operand1 +operand2;\
\cf5 else\cf4 \cf5 if\cf4 (operation == \cf6 '-'\cf4 ) \cf5 return\cf4 operand1 - operand2;\
\cf5 else\cf4 \cf5 if\cf4 (operation == \cf6 '*'\cf4 ) \cf5 return\cf4 operand1 * operand2;\
\cf5 else\cf4 \cf5 if\cf4 (operation == \cf6 '/'\cf4 ) \cf5 return\cf4 operand1 / operand2;\
\'a0\
\cf5 else\cf4 cout<<\cf6 "Unexpected Error \\n"\cf4 ;\
\cf5 return\cf4 -\cf8 1\cf4 ; \
\}\
}