Dasturlash II 7-hafta mavzu: shablonlar, vektorlar va steklar

Faza I I. Stekni tozalash.
Bunda operatorStack ning yuqorisidan boshlab, operatorStack gacha bo`shatiladi.
7.2-jadvalda (1 + 2) * 4 – 3 ifodaning ishlanishida algoritmning qo`llanilishi tasvirlangan.
7.2-jadval. Ifodaning hisoblanishi.

Ifoda	Tekshirish	Harakat	operandStack	operatorStack
(1 + 2) * 4 – 3	(	Phase 1.4		(
↑
(1 + 2) * 4 – 3	1	Phase 1.1	1	(
↑
(1 + 2) * 4 – 3	+	Phase 1.2	1	+ (
↑
(1 + 2) * 4 – 3	2	Phase 1.1	2 1	+ (
↑
(1 + 2) * 4 – 3	)	Phase 1.5	3
↑
(1 + 2) * 4 – 3	*	Phase 1.3	3	*
↑
(1 + 2) * 4 – 3	4	Phase 1.1	4 3	*
↑
(1 + 2) * 4 – 3	–	Phase 1.2	12	–
↑
(1 + 2) * 4 – 3	3	Phase 1.1	3 12	–
↑
(1 + 2) * 4 – 3	none	Phase 2	9
↑

7.6-kodli ro`yxatda bu masalaning dastur kodi berilgan.

7.6-kodli ro`yxat. IfodaniHisoblash.cpp
1 #include
2 #include
3 #include
4 #include
5 #include "ImprovedStack.h"
6
7 using namespace std;
8
9 // Ifodani sonlarga, operatorlarga va qavslarga ajratish
10 vector<string> ajratish(const string& ifoda);
11
12 // Ifodani hisoblash va natijani qaytarish
13 int ifodaniHisoblash(const string& ifoda);
14
15 // Amalni bajarish
16 void processAnOperator(
17 Stack<int>& operandStack, Stack<char>& operatorStack);
18
19 int main()
20 {
21 string ifoda;
22 cout << "Ifodani kiriting: ";
23 getline(cin, ifoda);
24
25 cout << ifoda << " = "
26 << ifodaniHisoblash(ifoda) << endl;
27
28 return 0;
29 }
30
31 vector<string> ajratish(const string& ifoda)
32 {
33 vector<string> v; // Satr sifatida ajratilgan bo`laklar uchun vektor
34 string sonlarSatri; // Sonli satr
35
36 for (unsigned i = 0; i < ifoda.length(); i++)
37 {
38 if (isdigit(ifoda[i]))
39 sonlarSatri.append(1, ifoda[i]); // Son qo`shish
40 else
41 {
42 if (sonlarSatri.size() > 0)
43 {
44 v.push_back(sonlarSatri); // Sonli satrni yozish
45 sonlarSatri.erase(); // Sonli satrni bo`shatish
46 }
47
48 if (!isspace(ifoda[i]))
49 {
50 string s;
51 s.append(1, ifoda[i]);
52 v.push_back(s); // Operator va qavslarni yozish
53 }
54 }
55 }
56
57 // So`nggi sonli satrni yozish
58 if (sonlarSatri.size() > 0)
59 v.push_back(sonlarSatri);
60
61 return v;
62 }
63
64 // Ifodani hisoblash
65 int ifodaniHisoblash(const string& ifoda)
66 {
67 // Operandlarni yozish uchun operandStack ni hosil qilish
68 Stack<int> operandStack;
69
70 // Operatorlarni yozish uchun operatorStack hosil qilish
71 Stack<char> operatorStack;
72
73 // Operandlar va operatorlarni ajratish
74 vector<string> bulaklar = ajratish(ifoda);
75
76 // Faza 1: Bulaklarni tekshirish
77 for (unsigned i = 0; i < bulaklar.size(); i++)
78 {
79 if (bulaklar[i][0] == '+' || bulaklar[i][0] == '-')
80 {
81 // Operator stekning yuqorisida joylashgan barcha +, -, *, / operatorlar
82 while (!operatorStack.empty()&&(operatorStack.peek()=='+'
83 || operatorStack.peek()=='-'||operatorStack.peek() == '*'
84 || operatorStack.peek() == '/'))
85 {
86 processAnOperator(operandStack, operatorStack);
87 }
88
89 // Operator stekka + yoki – operatorini qo`shish
90 operatorStack.push(bulaklar[i][0]);
91 }
92 else if (bulaklar[i][0] == '*' || bulaklar[i][0] == '/')
93 {
94 // Operator stekning yuqorisida joylashgan barcha * yoki / operatorlar
95 while (!operatorStack.empty()&&(operatorStack.peek()== '*'
96 || operatorStack.peek() == '/'))
97 {
98 processAnOperator(operandStack, operatorStack);
99 }
100
101 // Operator stekka * yoki / operatorini qo`shish
102 operatorStack.push(bulaklar[i][0]);
103 }
104 else if (bulaklar[i][0] == '(')
105 {
106 operatorStack.push('('); // Push '(' to stack
107 }
108 else if (bulaklar[i][0] == ')')
109 {
110 // '(' belgisi ko`ringuncha stekdagi barcha operatorlarni ishlatish
111 while (operatorStack.peek() != '(')
112 {
113 processAnOperator(operandStack, operatorStack);
114 }
115
116 operatorStack.pop(); // Stekdan '(' belgisini o`chirish
117 }
118 else
119 { // Operand tekshirildi. Operandni butun ko`rinishda stekka yozish.
120 operandStack.push(atoi(bulaklar[i].c_str()));
121 }
122 }
123
124 // Faza 2: Stekdagi barcha qolgan operatorlarni ishlatish
125 while (!operatorStack.empty())
126 {
127 processAnOperator(operandStack, operatorStack);
128 }
129
130 // Natijani qaytarish
131 return operandStack.pop();
132 }
133
134 // Bitta operatorning bajarilishi: Operatorni operatorStack dan olish va
135 // uni operandStack dagi operandlarga qo`llash
136 void processAnOperator(
137 Stack<int>& operandStack, Stack<char>& operatorStack)
138 {
139 char op = operatorStack.pop();
140 int op1 = operandStack.pop();
141 int op2 = operandStack.pop();
142 if (op == '+')
143 operandStack.push(op2 + op1);
144 else if (op == '-')
145 operandStack.push(op2 - op1);
146 else if (op == '*')
147 operandStack.push(op2 * op1);
148 else if (op == '/')
149 operandStack.push(op2 / op1);
150 }


Natija:

Ifodani kiriting: (13 + 2) * 4 – 3 (13 + 2) * 4 – 3 = 57

Ifodani kiriting: 5 / 4 + (2 - 3) * 5 5 / 4 + (2 – 3) * 5 = –4

Dastur 23-qatorda ifodani satr sifatida o`qiydi va ifodani hisoblash uchun evaluateExpression funksiyasini chaqiradi (26-qator).

evaluateExpression funksiyasi operandStack va operatorStack nomli ikkita stek hosil qiladi (68-, 70-qatorlar) va ifodadan sonlar, operatorlar va qavslarni ajratib olish uchun split funksiyasini chaqiradi (74-qator). Bo`laklar satrli vektorda yoziladi. Masalan, agar ifoda (13 + 2) * 4 – 3 bo`lsa, uning bo`laklari (, 13, +, 2, ), *, 4, –, va 3.
evaluateExpression funksiyasi for sikli orqali har bir bo`lakni tekshiradi (77-122-qatorlar). Agar bo`lak operand bo`lsa, uni operandStack ga qo`shadi (120-qator). Agar bo`lak + yoki – operatori bo`lsa (79-qator) va agar shundaylari bo`lsa, operatorStack dagi barcha operatorlarni ishga tushiradi (81-87-qatorlar) va yangi tekshirilgan operatorni stekka qo`shadi (90-qator). Agar bo`lak * yoki / operatori bo`lsa (92-qator) va agar shundaylari bo`lsa, operatorStack dagi barcha operatorlarni ishga tushiradi (95-99-qatorlar) va yangi tekshirilgan * va / operatorlarni stekka qo`shadi (102-qator). Agar bo`lak ( belgisi bo`lsa (104-qator), dastur uni operatorstack ga qo`shadi. Agar bo`lak ) belgisi bo`lsa (108-qator), operatorstack dagi barcha operatorlar ) belgisiga kelgunga qadar bajariladi (111-114-qatorlar) va ) belgisi stekdan olinadi.
Barcha bo`laklar ko`rib chiqilgandan so`ng, operatorstack dagi qolgan operatorlarni ishga tushiradi (125-128-qatorlar).
processAnOperator funksiyasi (136-15-qatorlar) opoeratorni ishga tushiradi. 139-qatorda funksiya operatorni va ikkita operandlarni operatorstack dan olib tashlaydi (mos ravishda, 139- hamda 140-141-qatorlar). Operatorga bo`gliq ravishda, operatsiyalarni amalga oshiradi va operatsiya natijasini operandStack dan qaytaradi (143-, 145-, 147-, 149-qatorlar).