Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ВНУТРІШНІ ФОРМИ ПОДАНННЯ ВХІДНОЇ ПРОГРАМИ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
ТГВ
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2010
Тип роботи:
Звіт
Предмет:
Лiнгвiстичне забезпечення САПР
Група:
КН
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
Національний університет «Львівська політехніка»
Кафедра САПР
Звіт з виконання
Лабораторної роботи №1
на тему:
ВНУТРІШНІ ФОРМИ ПОДАНННЯ ВХІДНОЇ ПРОГРАМИ
з курсу:
«Лінгвістичне забезпечення САПР»
1. МЕТА РОБОТИ
Закріпити навики одержання бездужкового польського запису, використовуючи метод Дейкстри і бінарні дерева.
2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Для оптимізації процесу компіляції первісна текстова програма перекладається у деяку внутрішню форму, зручнішу для подальшої машинної обробки. Проміжна програма виробляється синтаксичним аналізатором і відображає структуру первинної програми. У той самий час оператори проміжної програми розміщуються в тому випадку, в якому вони повинні виконуватись.
Найрозповсюдженішими формами подання вхідної програми є:
1) Бездужковий запис (польський запис);
2) Тетради;
3) Тріади;
4) Зв’язані спискові структури;
5) Зображаючі дерева.
ЗАПИС БЕЗДУЖКОВИЙ. АЛГОРИТМ ДЕЙКСТРИ.
Запис бездужковий – подання виразу, при якому порядок виконання операцій визначається її контекстом і позицією у формулі.
Існують два види бездужкових записів: прямий, або префікс ний і інверсний, або постфікс ний.
Для автоматизованих обчислень найзручніше використовувати постфікс ний запис бездужковий.
Відомо декілька методів отримання пост фіксовано польського запису. Найефективніший є алгоритм Дейкстри.
Цей метод базується на використанні стека для збереження знаків операцій.
Кожному обмежувачу, який входить у вираз, присвоюється пріоритет.
Для знаків операцій пріоритет зростає в порядку, зворотному до старшинства операцій. Алгоритмічні і логічні вирази розглядаються як вхідна стрічка символів зліва направо.
Операнди переписуються у вихідну стрічку, а знаки операцій поміщають у стек операцій.
Якщо пріоритет вхідного знака операцій дорівнює нулю або більший від пріоритету знака, який є на вершині стека, то новий знак додається до вершини стека. В протилежному випадку із стека «виштовхується» і переписується у вихідні стрічці знак, що розташований у вершині, а також наступні за ним знаки з пріоритетом більшим або таким, що дорівнює пріоритету вхідного знака. Після цього вхідний знак додається до вершини стека.
Обмежувачі
Пріоритет
( [ if
0
= ) then else
1
2
3
^
4
]
5
> ≥ = ≤ ≠ <
6
+ -
7
* / ÷ @
8
?
9
Деякі особливості має й робота з дужкам. Відкриваючі дужки мають нульовий пріоритет, просто записуються у вершину стеку і не виштовхують жодного знака. Виштовхувати відкриваючу дужку може тільки закриваюча. Закриваюча дужка має пріоритет один, який не перевищує пріоритету будь-якої операції. Поява закриваючої дужки викликає виштовхування усіх знаків операцій до найближчої дужки. В стек закриваюча дужка не записується і у вихідну стрічку не переноситься. Відкриваюча і закриваюча дужки взаємно знищується.
ФОРМУВАННЯ БЕЗДУЖКОВОГО ЗАПИСУ ЗА ДОПОМОГОЮ БІНАРНОГО ДЕРЕВА.
Арифметичний вираз можна подати у вигляді дерева. Вузли дерева відповідають операціям, а гілки – операндам. Ліва гілка, яка виходить з вузла, відповідає лівому операнду., права – правому. Операціям, які виконуються раніше, відповідають нижче розміщені вузли. Верхній вузол – корінь дерева відповідає операція, яка виконується останньою.
На рис. 2. показано дерево виразу: .
Рис. 2. Обхід дерева для одержання постфіксного польського запису .
Якщо, почавши з нижнього листка крайньої лівої гілки дерева, обійти усі листки і вузли дерева, так щоб гілки розглядались зліва направо, а вузол розглядався після обходу усіх гілок, що з нього виходять, то послідовність перегляду вузлів і листків дасть постфіксний польський запис.
На рис. 3. показано дерево виразу і порядок обходу для одержання префіксного польського запису.
Рис. 3. Обхід бінарного дерева для одержання префіксного польського запису .
Якщо, почавши з верхнього вузла, обійти усі вузли і листки дерева, так щоб верхній вузол розглядався раніше ніж нижній, і одразу після розгляду вузла проглядалися зліва направо гілки, які з нього виходять, то отримаємо префікс ний польський запис.
3. ВИКОНАННЯ РОБОТИ
ІНДИВІДУАЛЬНЕ ЗАВДАННЯ
Варіант №17
Скласти програму, яка за допомогою бінарного дерева перетворить у постфіксний польський запис вираз
ТЕКСТ ПРОГРАМИ НА С.
#include <stdio.h>
#include <string.h>
#include <graphics.h>
#include <conio.h>
char prefixNotation[100]={0}, postfixNotation[100]={0};
char priors[6][2] = { {'+',3},
{'-',3},
{'*',4},
{'/',4},
{'<',2},
{'o',1}};
char OVERPRIORITY = 6;
int radius=17;
char getPriority(char oper){
for(int i=0; i<6;i++){
if(oper==priors[i][0])
return priors[i][1];
}
return OVERPRIORITY;
}
void parse(char *code, int x, int y, int l)
{
// 1)only 1 element
if(strlen(code)==1){
setcolor(7);
pieslice(x,y,0,360,radius);
setcolor(3);
outtextxy(x-5,y-5,code);
prefixNotation[strlen(prefixNotation)] = code[0];
postfixNotation[strlen(postfixNotation)] = code[0];
return;
}
// 2)some string
// n-element number, prior-element priority
int n=0, prior= OVERPRIORITY;
for(int i=0; i<strlen(code); i++){
if(code[i]=='('){
int k=1;
while(k!=0){
i++;
if(code[i]==')'){
k--;
}else if(code[i]=='('){
k++;
}
}
continue;
}
if(getPriority(code[i])<prior){
//printf("Operator %c - priority - %d",code[i], getPriority(code[i]));
n=i;
prior = getPriority(code[i]);
}
}
// 2.1) into handles (code) and not unarniy
if(prior == OVERPRIORITY){
*(code+strlen(code)-1)=0;
parse(code+1, x, y, l);
return;
}
// 2.2) found operator
prefixNotation[strlen(prefixNotation)] = code[n];
char elem[2] ={0};
elem[0] = code[n];
*(code+n)=0;
setcolor(7);
line(x,y,x-l,y+50);
line(x,y,x+l,y+50);
pieslice(x,y,0,360,radius);
parse(code, x-l, y+50, l*0.5);
parse(code+n+1, x+l, y+50, l*0.5);
setcolor(3);
outtextxy(x-5,y-5,elem);
postfixNotation[strlen(postfixNotation)] = elem[0];
return;
}
void main(){
clrscr();
char code[100]={0};
printf("--Vvedit vuraz-->\n");
gets(code);
int gd=DETECT, gm;
initgraph(&gd, &gm, "c:\\tc3\\bgi " );
printf("\n %s",code);
parse(code, (640/2), 30, 150);
// printf("\n Prefix: ");
// printf(prefixNotation);
printf("\n Postfix: ");
printf(postfixNotation);
getch();
}
Обхід бінарного дерева для одержання постфіксний польський запис .
4. ВИСНОВОК
На цій лабораторній роботі, я вивчив і закріпити навики одержання бездужкового польського запису, використовуючи метод бінарні дерева. Написав програма, яка за принципом бінарного дерева перетворює вираз у постфіксний польський запис . Переконався, що вона працює і виводить коректний результат.
17.07.2020 15:07-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора