![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Пример. По введенной формуле необходимо построить ее постфиксную (польскую инверсную) запись (ПОЛИЗ). При вычислении выражений, записанных в ПОЛИЗе, операции выполняются в том порядке, в котором они встречаются при просмотре выражения слева направо, поэтому отпадает необходимость использования скобок и многократного сканирования выражения из-за различного приоритета операций. Например, выражению 2+3*4 соответсвует ПОЛИЗ 234*+, а выражению (a+(b^c)^d*(c+f/d) – ПОЛИЗ abc^d^+cfd/+*. Будем считать что в введенной формуле встречаются только операции +, -,*, / и буквы операнды.
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#define ZNAK (c=='*' || c=='/')
struct STACK
{
int info;
STACK *next;
};
//-------Функция добавления элемента в вершину стека-------
void push (STACK ** s, int i)
{
STACK * new_el;
new_el= new (STACK);
new_el->info=i;
new_el->next=*s;
*s=new_el;
}
//-----Функция удаления верхнего элемента из стека--------
int pop (STACK ** s, int * error)
{
STACK * old=*s;
int info=0;
if (*s) //если стек не пуст
{
info=old->info;
*s=(*s)->next;
delete old;
*error=0; //элемент успешно удален
}
else *error=1;
return info;
}
//--Функция получение значения из стека (без удаления элемента)--
int peek (STACK ** s, int *error)
{
if (*s)
{
*error=0;
return (*s)->info;
}
else {*error=1; return 0;}
}
void main ()
{
char s[80], s1[80];//массив для считывания формулы и для записи ПОЛИЗа
char c; //вспомогательный символ
STACK *st=NULL;
cout<<"vvedite formulu ";
gets(s);
int l= strlen (s);
push(&st,'(');//заносим '(' в стек
int k=0, er;
for (int i=0; i<l; i++) //просматриваев выражение
//cлева направо
{
if (isalpha(s[i])) s1[k++]=s[i];
//isalpha(x), функция описанная в сtype.h, проверяет,
//является ли x латинской буквой
else if (s[i]=='(') push (&st, '(');
else if (s[i]==')')
while ((c=pop (&st, &er))!='(') s1[k++]=c;
else
switch (s[i])
{
case '+':case'-':
while ((c=peek(&st, &er))!='(') s1[k++]=pop(&st, &er);
case '*':case'/':
while ((c=peek(&st, &er))!='(')
{if (!ZNAK) break;
s1[k++]=pop(&st, &er);
}
push(&st,s[i]); break;
default: cout<<"Nevernuy simvol "<< s[i]; getch(); exit(-1);
}
}
//в заключение выполняются такие же действия,
//как если бы встретилась закрывающая скобка
while ((c=pop (&st, &er))!='(') s1[k++]=c;
s1[k]='\0';
cout<<"POLIS "<<s1;
getch();
}
Комментарий. Когда в записи формулы встречается знак операции - не скобка и не операнд – то с вершины стека извлекаеются (до ближайшей скобки, которая сохраняется в стеке) знаки операций, старшество которых больше или равно старшенству данной операции, и они заносятся в выходной массив, после чего рассматриваемый знак заносится в стек.
1. В файле находится текст программы на языке С++. Написать, использую стек, препроцессор, проверяющий правильность вложенности циклов в этой программе.
2. В файле находится текст, в котором используют скобки трех типов: (), ||,{}. Используя стек, проверить соблюден ли баланс скобок в тексте.
3. Используя стек, решить задачу: в файле находится текст, сбалансированный по круглым скобкам. Требуется для каждой пары соответствующих открывающей и закрывающей скобок напечатать номера их позиций в тексте, упорядочив пары номеров по возрастанию номеров позиций закрывающих скобок. Например, для текса a+(45-f(x)*(b-c)) надо напечатать 8 10, 12 16, 3 17
4. Используя очередь, решить задачу: в файле находится текст, сбалансированный по круглым скобкам. Требуется для каждой пары соответствующих открывающей и закрывающей скобок напечатать номера их позиций в тексе, упорядочив пары номеров по возрастанию номеров позиций открывающих скобок. Например, для текса a+(45-f(x)*(b-c)) надо напечатать 3 17, 8 10, 12 16
5. Используя стек, проверить, является ли содержимое текстового файла правильно записью формулы следующего вида:
<формула>::=<терм>|<терм>+<формула>|<терм>-<формула>
<терм>::=<имя>|<формула>
<имя>::=x | y |z
6. В текстовом файле записана без ошибок формула следующего вида:
<формула>::=<цифра>|M(<формула>,<формула>) |m(<формула>,<формула>)
<цифра>::=0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
M обозначает функцию максимума, а m – функцию минимума
Используя стек, вычислить как целое число значение заданной формулы. Например, М(5,m(6,8))=6.
7. В текстовом файле записано без ошибок логическое выражение следующего вида:
<выражение>::=true | false |! <выражение> | <выражение>&&<выражение> | <выражение>||<выражение>
Используя стек, вычислить значение этого выражения с учетом общепринятого приоритета операций.
8. Используя стек вычислить как целое число значение выражения, записанного в ПОЛИЗе.
9. Используя стек, выражение, записанное в ПОЛИЗе, перевести в инфиксную форму.
10. Используя стек, переписать содержимое текстового файла, разделенного на строки, в другой файл. Причем, необходимо переносить в конец каждой строки все входящие в нее цифры в обратном порядке.
11. Используя очередь за один просмотр файла, содержащего целые числа, распечатать файл в следующем виде: сначала все числа меньшие A, затем все числа из интервала [A, B] и затем - все остальные числа.
12. Используя стек, проверить, является ли содержимое текстового файла правильно записью формулы следующего вида:
<формула>::=<цифра>|(<формула><знак><формула>)
<знак>::=+|-|*
<имя>::=x | y |z
<цифра>::=0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Дата публикования: 2015-10-09; Прочитано: 439 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!