Қавсҳои се навъро бо стек санҷед, бифаҳмед, кай ҳисобкунак кифоя аст, ифодаи постфиксиро ҳисоб кунед ва хурдтарини стекро ҳозир нигоҳ доред.
Масъалаҳо оид ба санҷиши қавсҳо, ҳарфҳое, ки ҷуфт-ҷуфт нест мешаванд, ҳисобкунаки постфиксӣ ва стеке, ки хурдтарини худро медонад.
stack<char> st; st.push('a'); st.push('b'); cout << st.top(); st.pop(); cout << st.top();st холӣ аст. Оё даъвати st.top() бехатар аст?ba: b дар боло аст ва баъд аз pop() боло a мешавад. 2. Не: ҷузъи боло нест. Барнома метавонад вайрон шавад ё маълумоти беарзиш бихонад.Сатр аз қавсҳои
(,),[,],{ва}иборат аст. Он мутавозин аст, агар ҳар қавси кушода бо қавси ҳамон намуд пӯшида шавад ва ҷуфтҳо дуруст дар ҳам бошанд. Агар сатр мутавозин бошад,YESчоп кунед, вагарнаNO.
Вуруд
Баромад
Қавсе, ки аввал бояд пӯшида шавад, ҳамонест, ки охирин кушода шуд. Ин айнан болои стек аст.
pop. Ҷуфт анҷом ёфт.Се тарзи хато:
([)]: ) меояд, дар ҳоле ки дар боло [ аст. Намуди нодуруст.()): )-и дуюм меояд ва стек холӣ аст. Чизе барои пӯшидан нест.((): сатр бо ( дар стек тамом мешавад. Ҳеҷ гоҳ пӯшида нашуд.Акнун шумо стек ҳастед.
Агар танҳо ( ва ) бошад, ҳар ҷузъи стек якхела аст: (. Фақат андоза муҳим аст, барои ҳамин int ин корро мекунад:
Он чоп мекунад, ки чандто ) ҷуфт наёфт ва чандто ( пӯшида нашуд. Мутавозин он вақт аст, ки ҳарду 0 бошанд. Барои ))((() он 2 2 чоп мекунад.
Мо 3 + 4-ро менависем ва аломати амал миёни ададҳост. Дар навишти постфиксӣ аломати амал баъд аз онҳо меояд: 3 4 +. Қавс лозим нест ва қоидаи он ки чӣ аввал иҷро мешавад ҳам лозим нест: тартиби токенҳо ҳама чизро мегӯяд. (6 - 2) * 3 чунин навишта мешавад: 6 2 - 3 *.
Стек онро дар як гузариш ҳисоб мекунад:
y. Зери он x аст. x op y-ро гузоред. Барои - тартиб муҳим аст: 6 2 - 4 аст, на −4.Дар охир як адад мемонад: ҷавоб.
Сатри аввал
m-ро дорад, сатри дуюмmтокени ифодаи постфиксиро. Токен адади бутун аст, шояд манфӣ, ё яке аз+,-,*. Қиматро чоп кунед.
Вуруд
Баромад
Токен танҳо вақте амал аст, ки айнан +, - ё * бошад. Барои ҳамин -3 адад аст. stoll матнро ба long long мегардонад. long long-ро дар стек нигоҳ доред: якчанд зарб барои пур шудани int кифоя аст.
Баъд
qфармон меояд.push xададиx-ро ба стек мегузорад.popболоро мебардорад, ё агар стек холӣ бошад, ҳеҷ кор намекунад.minхурдтарин адади стекро чоп мекунад, ёempty.
Вуруд
Баромад
Ҳар дафъа ҷустуҷӯи тамоми стек барои min хеле суст аст. Беҳтараш қимати хурдтаринро аз ҳар ҷузъ то поён ба ёд гиред. Стеки дуюм, mins, ҳамон баландии vals-ро дорад. Вақте x гузошта мешавад, mins min(x, the old top of mins)-ро мегирад. pop аз ҳарду стек як ҷузъ мебардорад. Чизеро ислоҳ кардан лозим нест, зеро ҷузъҳои поён тағйир наёфтанд.
Шумо метавонед ҷуфтҳои (қимат, хурдтарини зер)-ро дар як стек нигоҳ доред. Ғоя ҳамон аст.
pop. Стек дар охир бояд холӣ бошад.y, баъд x-ро мебардорад ва x op y-ро мегузорад.([]{()})
YES
Постфиксро навишти поляки баръакс низ меноманд. Мантиқдони поляк Ян Лукасевич дар солҳои 1920-ум аломати амалро пеш аз ададҳо менавишт, то бе қавс кор кунад. Постфикс ҳамон тартиби чаппашуда аст. Калкуляторҳои кисагии Hewlett-Packard, аз HP-35 дар соли 1972, бо навишти постфиксӣ кор мекарданд: барои ҷамъ кардани 3 ва 4 шумо 3, ENTER, 4, +-ро пахш мекардед. Дар дохил стек ҳамон корро мекард, ки барномаи ин дарс.
x - y-ро бо тартиби дуруст нигоҳ медорам.Нависед: чаро ҳисобкунак бо қавсҳои се намуд кор намекунад?
#include <bits/stdc++.h>
using namespace std;
bool matches(char open, char close) {
if (open == '(') {
return close == ')';
}
if (open == '[') {
return close == ']';
}
return close == '}';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s;
cin >> s;
stack<char> st;
bool ok = true;
for (char c : s) {
if (c == '(' || c == '[' ||
c == '{') {
st.push(c);
} else {
if (st.empty() ||
!matches(st.top(), c)) {
ok = false;
break;
}
st.pop();
}
}
if (!st.empty()) {
ok = false;
}
cout << (ok ? "YES" : "NO") << "\n";
return 0;
}
Қимати ифодаи постфиксии 4 2 5 * + 1 - чанд аст?
Ду стеки баландии якхела. Дар vals қиматҳо истодаанд, дар mins барои ҳар қимат хурдтарин қимат аз он то поён. Ба vals 5, 3, 8 ва 1-ро мегузоранд, баъд ду маротиба мегиранд (ҳар амали pop аз ҳарду стек як ҷузъро мебарад). Акнун mins.top() ба чанд баробар аст?
Сикли ҳисобкунаки дарс сатри (()(()-ро мехонад. Дар охир open ба чанд баробар аст?
9
5 1 2 + 4 * + -3 -
20
11
push 6
push 9
push 2
min
pop
min
pop
pop
min
push 7
min
2
6
empty
7
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s;
cin >> s;
int open = 0, broken = 0;
for (char c : s) {
if (c == '(') {
open++;
} else if (open > 0) {
open--;
} else {
broken++;
}
}
cout << broken << " "
<< open << "\n";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int m;
cin >> m;
stack<long long> st;
for (int i = 0; i < m; i++) {
string tok;
cin >> tok;
if (tok == "+" || tok == "-" ||
tok == "*") {
// y қимати дертар
long long y = st.top();
st.pop();
long long x = st.top();
st.pop();
if (tok == "+") {
st.push(x + y);
} else if (tok == "-") {
st.push(x - y);
} else {
st.push(x * y);
}
} else {
st.push(stoll(tok));
}
}
cout << st.top() << "\n";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int q;
cin >> q;
// mins.top(): хурдтарин дар vals
stack<int> vals, mins;
for (int i = 0; i < q; i++) {
string cmd;
cin >> cmd;
if (cmd == "push") {
int x;
cin >> x;
int mn = x;
if (!mins.empty()) {
mn = min(x, mins.top());
}
vals.push(x);
mins.push(mn);
} else if (cmd == "pop") {
if (!vals.empty()) {
vals.pop();
mins.pop();
}
} else if (vals.empty()) {
cout << "empty\n";
} else {
cout << mins.top() << "\n";
}
}
return 0;
}
if (c == '(') {
open++;
} else if (open > 0) {
open--;
} else {
broken++;
}