Суть стандартних функцій роботи зі стеком ілюструє наступний код (стек при цьому зберігається у масиві)
# include<iostream>
# include<cstdlib>
# include<cstdio>
usingnamespace std;
int st[1000]; // стек, який зберігатиметься у масиві
int st_size; // розмір стеку
void push (int x)
{
st[++st_size] = x; // збільшуємо розмір стеку та записуємо в нього елемент
}
void pop ()
{
st[st_size--] = 0; // обнуляємо верхній елемент та зменшуємо розмір стеку
}
int top ()
{
return st[st_size]; // повертаємо значення верхнього елемента
}
int size ()
{
return st_size; // повертаємо розмір стеку
}
bool empty ()
{
if (st_size >= 1) // перевіряємо, чи є у стеку хоча б 1 елемент
returntrue;
returnfalse; // інакше повертаємо false
}
int main ()
{
push (1); // [1]
push (2); // [1][2]
push (3); // [1][2][3]
cout << top () << "\n"; // [1][2]->[3]<-, виводимо "3"
push (4); // [1][2][3][4]
cout << top () << "\n"; // [1][2][3]->[4]<-, виводимо "4"
pop (); // [1][2][3]
pop (); // [1][2]
pop (); // [1]
cout << top () << "\n"; // ->[1]<-,виводимо "1"
system ("pause");
return 0;
}
Задача 1. З клавіатури вводяться текстові рядки. Якщо зчитано слово, то записати його у стек. Якщо зчитано "-”, то видалити зі стеку останній елемент. Якщо зчитано "*", то надрукувати стек
// створення стеку типу string
// створення змінної для введення з клавіатури
// введення рядка з клавіатури
// поки введений рядок не рівний "*"
{
// якщо введений рядок не рівний "-"
// записати у стек введений рядок
// інакше
// видалити зі стеку останній елемент
// введення нового рядка з клавіатури
}
// поки стек не порожній
{
// друкувати верхній символ стеку
// видалити зі стеку останній елемент
}
Задача 2. Перевірка правильності розстановки дужок одного типу
( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )
// створення стеку типу char
// створення змінної для введення з клавіатури
// введення рядка з клавіатури
// номер символа, який розглядається
// показник видалення з порожнього стека = false
// поки не дійдемо до останнього символа
{
// якщо поточний символ = '('
// записати символ у стек
// якщо поточний символ = ')'
// стек не порожній
// видалити символ зі стеку
// інакше
{
// показник стає true
// достроковий вихід з циклу break
}
// переходимо до наступного символу
}
// якщо показник true або стек не порожній (залишились дужки)
// надрукувати Ні
// інакше
// надрукувати Так
Тестові дані до задачі 2
1 (((A)*(B-C)-D)/2) так
2 (A+B*(C-D) ні
3 X-((A-B)*C)+(D/(E+F))/Y так
4 A-(X/(B*C)+D/(E+F)) так
5 (D+(F-(A-B)*C)+D/(E+F)))( ні
6 )((A-B)*C)+(D/(E+F))) ні
7 D+(F-(A-B)/F+(K))*C+(D/(E+F) ні
8 D+(F-(A-B/F)+K)*C)/D/(E+F) ні
9 (A+(C+B))/(K-D)*(B+F)/(A+B*C) так
10 (A+B*(C-D)) так
Задача 3. Перевірка правильності розстановки дужок різних типів ( [ ) ] - помилка
При записуванні у стек потрібно враховувати всі типи відкриваючих дужок.
При видаленні зі стеку - можна видаляти лише дужку такого ж типу, як остання записана. Інакше - помилка
Тестові дані до задачі 3
1 (((A)*[B-C]-D)/2) так
2 (A-(B*[(C+D)-E])/F)) ні
3 ([()[]()])() так
4 ([([]()]))() ні
5 ([([]())])() так
Розв'язки задач:
# include
# include
#include
using namespace std;
int main ()
{
setlocale(LC_ALL, "Ukrainian");
stack < string > st; // створення стеку типу string
string a; // створення змінної для введення з клавіатури
cin >> a; // введення рядка з клавіатури
while (a!="*") // поки введений рядок не рівний "*"
{
if (a !="-") // якщо введений рядок не рівний "-"
st.push (a); // записати у стек введений рядок
else // інакше
st.pop(); // видалити зі стеку останній елемент
cin >> a; // введення нового рядка з клавіатури
}
while (st.empty() !=true) // поки стек не порожній
{
cout << st.top () << "\n"; // друкувати верхній символ стеку
st.pop(); // видалити зі стеку останній елемент
}
system ("pause");
return 0;
}
Задача 2
# include
# include
#include
using namespace std;
int main ()
{
setlocale(LC_ALL, "Ukrainian");
stack < char > st; // створення стеку типу char
string a; // створення змінної для введення з клавіатури
cin >> a; // введення рядка з клавіатури
int symb=0; // номер символа, який розглядається
bool pok=false; // показник видалення з порожнього стека = false
while (a[symb]<=a.length()) // поки не дійдемо до останнього символа
{
if (a[symb]=='(') // якщо поточний символ = '('
st.push(a[symb]); // записати символ у стек
if (a[symb]==')') // якщо поточний символ = ')'
if (st.empty() != true) // стек не порожній
st.pop(); // видалити символ зі стеку
else // інакше
{
pok=true; // показник стає true
break; // достроковий вихід з циклу break
}
symb=symb+1; // переходимо до наступного символу
}
if ((pok==true) || (st.empty() != true)) // якщо показник true або стек не порожній (залишились дужки)
cout <<"Hi" << "\n"; // надрукувати Ні
else // інакше
cout <<"Tak" << "\n"; // надрукувати Так
system ("pause");
return 0;
}
Last modified: Wednesday, 22 October 2014, 7:00 AM
