Использование стека для вычисления выражений

Август 20, 2022

Главная
Информатика
Использование стека для вычисления выражений

Содержание

2. Стек Стек – это линейная структура данных, в которой добавление и удаление элементов возможно только с
3. Пример задачи Задача: вводится символьная строка, в которой записано выражение со скобками трех типов: [], {}
4. Решение задачи со скобками Алгоритм: в начале стек пуст; в цикле просматриваем все символы строки по
5. Реализация стека (массив) Структура-стек: const MAXSIZE = 100; struct Stack { char data[MAXSIZE]; // стек на
6. Реализация стека (массив) char Pop ( Stack &S ) { if ( S.size == 0 )
7. Программа void main() { char br1[3] = { '(', '[', '{' }; char br2[3] = {
8. Обработка строки (основной цикл) for ( i = 0; i { for ( k = 0;
9. Реализация стека (список) Добавление элемента: Структура узла: struct Node { char data; Node *next; }; typedef
10. Реализация стека (список) Снятие элемента с вершины: char Pop (PNode &Head) { char x; PNode q
11. Вычисление арифметических выражений a b + c d + 1 - / Как вычислять автоматически: Инфиксная
12. Запишите в постфиксной форме (32*6-5)*(2*3+4)/(3+7*2) (2*4+3*5)*(2*3+18/3*2)*(12-3) (4-2*3)*(3-12/3/4)*(24-3*12)
13. Вычисление выражений Постфиксная форма: a b + c d + 1 - / Алгоритм: взять очередной
14. Получение постфиксной формы из скобочной с помощью стека Во-втоpых, получение обpатной польской записи из исходного выpажения
15. Получение постфиксной формы из скобочной с помощью стека Пpосматpивается исходная стpока символов слева напpаво, опеpанды сразу
16. #include #include #include using namespace std; int calc(string r){…} string revpol(string s){…} main(){ string s,r; getline(cin,s);
17. string revpol(string s){ string r="",p="()+-*/^"; stack v; int j=0,k,q[7]={0,1,2,2,3,3,4}; for(auto e:s){ if(e>='0'&&e else { if(v.empty()||e=='(') v.push(e);
18. int calc(string r){ // для однозначных операндов >=0 stack v;int a,b; for(auto e:r){ if(e>='0‘ and e
20. Скачать презентацию

Слайд 2

Стек
Стек – это линейная структура данных, в которой добавление и удаление

элементов возможно только с одного конца (вершины стека). Stack = кипа, куча, стопка (англ.)
LIFO = Last In – First Out
«Кто последним вошел, тот первым вышел».
Операции со стеком:
добавить элемент на вершину (Push = втолкнуть);
снять элемент с вершины (Pop = вылететь со звуком).

Слайд 3

Пример задачи
Задача: вводится символьная строка, в которой записано выражение со скобками

трех типов: [], {} и (). Определить, верно ли расставлены скобки (не обращая внимания на остальные символы). Примеры:
[()]{} ][ [({)]}
Упрощенная задача: то же самое, но с одним видом скобок.
Решение: счетчик вложенности скобок. Последовательность правильная, если в конце счетчик равен нулю и при проходе не разу не становился отрицательным.

Слайд 4

Решение задачи со скобками
Алгоритм:
в начале стек пуст;
в цикле просматриваем все символы

строки по порядку;
если очередной символ – открывающая скобка, заносим ее на вершину стека;
если символ – закрывающая скобка, проверяем вершину стека: там должна быть соответствующая открывающая скобка (если это не так, то ошибка);
если в конце стек не пуст, выражение неправильное.

[ ( ( ) ) ] { }

Слайд 5

Реализация стека (массив)
Структура-стек:
const MAXSIZE = 100;
struct Stack {
char data[MAXSIZE]; //

стек на 100 символов
int size; // число элементов
};

Добавление элемента:

int Push ( Stack &S, char x )
{
if ( S.size == MAXSIZE ) return 0;
S.data[S.size] = x;
S.size ++;
return 1;
}

ошибка: переполнение стека

добавить элемент

нет ошибки

Слайд 6

Реализация стека (массив)
char Pop ( Stack &S )
{
if ( S.size ==

0 ) return char(255);
S.size --;
return S.data[S.size];
}

Снятие элемента с вершины:

Пусто й или нет?

int isEmpty ( Stack &S )
{
if ( S.size == 0 )
return 1;
else return 0;
}

ошибка: стек пуст

int isEmpty ( Stack &S )
{
return (S.size == 0);
}

Слайд 7

Программа
void main()
{
char br1[3] = { '(', '[', '{' };
char

br2[3] = { ')', ']', '}' };
char s[80], upper;
int i, k, error = 0;
Stack S;
S.size = 0;
printf("Введите выражение со скобками > ");
gets ( s );
... // здесь будет основной цикл обработки
if ( ! error && (S.size == 0) )
printf("\nВыpажение пpавильное\n");
else printf("\nВыpажение непpавильное\n");
}

открывающие скобки

закрывающие скобки

то, что сняли со стека

признак ошибки

Слайд 8

Обработка строки (основной цикл)
for ( i = 0; i < strlen(s);

i++ )
{
for ( k = 0; k < 3; k++ )
{
if ( s[i] == br1[k] ) // если открывающая скобка
{
Push ( S, s[i] ); // втолкнуть в стек
break;
}
if ( s[i] == br2[k] ) // если закрывающая скобка
{
upper = Pop ( S ); // снять верхний элемент
if ( upper != br1[k] ) error = 1;
break;
}
}
if ( error ) break;
}

цикл по всем символам строки s

цикл по всем видам скобок

ошибка: стек пуст или не та скобка

была ошибка: дальше нет смысла проверять

Слайд 9

Реализация стека (список)
Добавление элемента:
Структура узла:
struct Node {
char data;
Node *next;
};
typedef

Node *PNode;

void Push (PNode &Head, char x)
{
PNode NewNode = new Node;
NewNode->data = x;
NewNode->next = Head;
Head = NewNode;
}

Слайд 10

Реализация стека (список)
Снятие элемента с вершины:
char Pop (PNode &Head) {
char

x;
PNode q = Head;
if ( Head == NULL ) return char(255);
x = Head->data;
Head = Head->next;
delete q;
return x;
}

Изменения в основной программе:

Stack S;
S.size = 0;
...
if ( ! error && (S.size == 0) )
printf("\nВыpажение пpавильное\n");
else printf("\nВыpажение непpавильное \n");

PNode S = NULL;

(S == NULL)

стек пуст

Слайд 11

Вычисление арифметических выражений
a b + c d + 1 - /
Как

вычислять автоматически:

Инфиксная запись
(знак операции между операндами)

(a + b) / (c + d – 1)

необходимы скобки!

Постфиксная запись (знак операции после операндов)

польская нотация,
Jan Łukasiewicz (1920)

скобки не нужны, можно однозначно вычислить!

Префиксная запись (знак операции до операндов)

/ + a b - + c d 1

обратная польская нотация,
F. L. BauerF. L. Bauer and E. W. Dijkstra

a + b

c + d

c + d - 1

Слайд 12

Запишите в постфиксной форме
(326-5)(23+4)/(3+72)
(24+35)(23+18/32)(12-3)
(4-23)(3-12/3/4)(24-312)

Слайд 13

Вычисление выражений
Постфиксная форма:
a b + c d + 1 - /

Алгоритм:
взять очередной элемент;
если это не знак операции, добавить его в стек;
если это знак операции, то
взять из стека два операнда;
выполнить операцию и записать результат в стек;
перейти к шагу 1.

X =

Слайд 14

Получение постфиксной формы из скобочной с помощью стека
Во-втоpых, получение обpатной польской

записи из исходного выpажения может осуществляться весьма пpосто на основе пpедложенного Дейкстpой алгоpитма.
Для этого вводится понятие стекового пpиоpитета опеpаций:

Слайд 15

Получение постфиксной формы из скобочной с помощью стека
Пpосматpивается исходная стpока символов

слева напpаво, опеpанды сразу пеpеписываются в выходную стpоку, а знаки опеpаций заносятся в стек так:
а) если стек пуст, то опеpация из входной стpоки пеpеписывается в стек;
б) если очеpедной символ из исходной стpоки есть откpывающая скобка, то он пpоталкивается в стек;
в) закpывающая кpуглая скобка выталкивает все опеpации из стека до ближайшей откpывающей скобки, сами скобки в выходную стpоку не пеpеписываются, а уничтожают дpуг дpуга.
г) опеpация выталкивает из стека все опеpации с большим или pавным пpиоpитетом в выходную стpоку, после чего сама операция заталкивается в стек;
Пpоцесс получения обpатной польской записи выpажения (A+B)*(C+D)-E:
Пpосматpиваемый
символ 1 2 3 4 5 6 7 8 9 10 11 12 13
Входная строка ( A + B ) * ( C + D ) - E
Состояние стека ( ( +( +( * (* (* +(* +(* * - -
Выходная строка A B + C D + * E -

Слайд 16

#include
#include
#include
using namespace std;
int calc(string r){…}
string revpol(string s){…}
main(){ string s,r;
getline(cin,s);
r=revppol(s);
cout< cout<}
На

С++ можно и нужно использовать библиотеки STL:

Слайд 17

$string revpol(string s){ string r="",p="()+-*/^"; stack v; int j=0,k,q[7]={0,1,2,2,3,3,4}; for(auto e:s){$

string revpol(string s){ string r="",p="()+-*/^"; stack v;
int j=0,k,q[7]={0,1,2,2,3,3,4};
for(auto e:s){
if(e>='0'&&e<='9')

r+=e;
else {
if(v.empty()||e=='(') v.push(e);
else if(e==')'){
while(v.top()!='(') {r+=v.top();v.pop();}
v.pop(); }
else{ k=q[p.find(e)];
while(!v.empty()&&v.top()!='('&&k<=q[p.find(v.top())])
{ r+=v.top();v.pop(); }
v.push(e); }
}
}
while(!v.empty()){r+=v.top();v.pop();}
return r;
}

Слайд 18

int calc(string r){ // для однозначных операндов >=0
stack v;int a,b;

for(auto e:r){
if(e>='0‘ and e<='9')
v.push(e-’0’);
else {b=v.top(); v.pop(); a=v.top(); v.pop();
if(e=='+')v.push(a+b);
if(e=='-')v.push(a-b);
if(e=='*')v.push(a*b);
if(e=='/')if(b==0){cout<<"Error /0!";return 0;}
else v.push(a/b);
if(e=='^')v.push(pow(a,b));} }
if(!v.empty()){a=v.top(); v.pop();return a;} else return 0;
}

Использование стека для вычисления выражений

Содержание

СтекСтек – это линейная структура данных, в которой добавление и удаление

Пример задачиЗадача: вводится символьная строка, в которой записано выражение со скобками

Решение задачи со скобкамиАлгоритм:в начале стек пуст;в цикле просматриваем все символы

Реализация стека (массив)Структура-стек:const MAXSIZE = 100;struct Stack { char data[MAXSIZE]; //

Реализация стека (массив)char Pop ( Stack &S ){if ( S.size ==

Программаvoid main(){ char br1[3] = { '(', '[', '{' }; char

Обработка строки (основной цикл)for ( i = 0; i < strlen(s);

Реализация стека (список)Добавление элемента:Структура узла:struct Node { char data; Node *next; };typedef

Реализация стека (список)Снятие элемента с вершины:char Pop (PNode &Head) { char

Вычисление арифметических выраженийa b + c d + 1 - /Как

Запишите в постфиксной форме(32*6-5)*(2*3+4)/(3+7*2)(2*4+3*5)*(2*3+18/3*2)*(12-3)(4-2*3)*(3-12/3/4)*(24-3*12)

Вычисление выраженийПостфиксная форма:a b + c d + 1 - /

Получение постфиксной формы из скобочной с помощью стекаВо-втоpых, получение обpатной польской

Получение постфиксной формы из скобочной с помощью стекаПpосматpивается исходная стpока символов

#include #include #include using namespace std;int calc(string r){…}string revpol(string s){…}main(){ string s,r; getline(cin,s); r=revppol(s); cout< cout<}На

string revpol(string s){ string r="",p="()+-*/^"; stack v; int j=0,k,q[7]={0,1,2,2,3,3,4}; for(auto e:s){ if(e>='0'&&e<='9')

int calc(string r){ // для однозначных операндов >=0 stack v;int a,b;

Похожие презентации