АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Пример реализации

Читайте также:
  1. III. Психические свойства личности – типичные для данного человека особенности его психики, особенности реализации его психических процессов.
  2. IV. Механизмы и основные меры реализации государственной политики в области развития инновационной системы
  3. X. примерный перечень вопросов к итоговой аттестации
  4. Анализ выполнения договорных обязательств и реализации продукции
  5. Анализ особенностей производства, использования и реализации готовой продукции растениеводства и животноводства
  6. Анализ реализации продукции предприятием
  7. Анализ факторов и резервов увеличения выпуска и реализации продукции
  8. Анализ факторов изменения объема реализации продукции
  9. Анализ финансовых результатов от прочей реализации и финансовых вложений.
  10. Анализ финансовых результатов от реализации продукции, работ и услуг
  11. Аудит операций по учету готовой продукции и ее реализации
  12. Аудит учета готовой продукции и ее реализации

Пусть задано выражение a + b * c +(d * e + f)* g. Необходимо записать это выражение в постфиксной форме. Правильным ответом будет выражение abc *+ de * f + g *+. Решаем эту задачу, используя стек.

Пусть исходная информация хранится в строке S =” a + b * c +(d * e + f)* g ”. Результат будем получать в строке В.

Начинаем последовательно просматривать символы исходной строки, причем стек пуст и В – пустая строка.

Букву «a» помещается в строку В, а операцию «+» помещаем в стек. Букву «b» помещаем в строку В. На этот момент стек и строка В выглядят следующим образом:

  В = ” ab
+  

Операцию «*» помещаем в стек, т.к. элемент в вершине стека имеет более низкий приоритет. Букву «с» помещаем в строку В, после чего имеем

  В = ” abс
*  
+  

Следующий символ строки S «+». Анализируем стек и видим, что элемент в вершине стека «*» и следующий за ним «+» имеют приоритеты не ниже текущего, следовательно, обе операции извлекаем из стека и помещаем в строку В, а текущий элемент помещаем в стек. В итоге имеем

  В = ” abс *+”
+  

Далее в строке S следует символ «(», его помещаем в стек, а букву «d» помещаем в строку В, в результате получается

  В = ” abс *+ d
(  
+  

Следующий в строке S символ «*». Так как открывающую скобку нельзя извлечь из стека до тех пор, пока не встретилась закрывающая, то «*» помещаем в стек. Букву «e» помещаем в строку В:

  В = ” abс *+ de
*  
(  
+  

Следующий прочитанный символ «+», и т.к. элемент стека «*» имеет более высокий приоритет, то извлекаем его из стека и помещаем в строку В, а текущий символ «+» помещаем в стек. Символ «f» помещаем в строку В:

  В = ” abс *+ de * f
+  
(  
+  

Далее в строке S идет закрывающая скобка, все элементы стека до символа «)» помещаем в строку В (это элемент «+»), а сам символ «(» извлекаем из стека. Обе скобки игнорируются:

  В = ” abс *+ de * f +”
+  

Операцию «*» помещаем в стек, а букву «g» – в строку В:

  В = ”abс*+de*f+g”
*  
+  

Все символы строки S рассмотрены, следовательно, анализируем состояние стека, если он не пуст, то переписываем все его элементы в строку В:

  В = ” abс *+ de * f + g *+”

Таким образом, просмотрев исходную информацию только один раз, мы решили поставленную задачу.

Текст программы, реализующий рассмотренный алгоритм, может иметь следующий вид:

...

struct Stack {

char c; // Символ операции

Stack *Next;

};

int Prior (char);

Stack* InS(Stack*,char);

Stack* OutS(Stack*,char*);

void main ()

{

Stack *t, *Op = NULL; // Стек операций Op – пуст

char a, In[50], Out[50]; // Входная In и выходная Out строки

int k = 0, l = 0; // Текущие индексы для строк

puts(" Input formula: "); gets(In);

while (In[k]!= '\0') { // Анализируем символы строки In

// Если символ «)», выталкиваем из стека в выходную строку все операции

if (In[k] == ')') {

while ((Op -> c)!= '(') { // до открывающей скобки

Op = OutS(Op,&a); // Считываем элемент из стека

if (!Op) a = '\0';

Out[l++] = a; // и записываем в строку Out.

}

t = Op; // Удаляем из стека открывающую скобку

Op = Op -> Next;

free(t);

}

// Если символ строки In – буква, заносим ее в строку Out

if (In[k] >= 'a' && In[k] <= 'z') Out[l++] = In[k];

// Если символ – открывающая скобка, записываем ее в стек

if (In[k] == '(') Op = InS(Op,In[k]);

/* Если символ – знак операции, переписываем из стека в строку Out все операции с большим или равным приоритетом */

if (In[k] == '+' || In[k] == '–' || In[k] == '*' || In[k] == '/') {

while (Op!= NULL && Prior (Op -> c) >= Prior (In[k])) {

Op = OutS(Op,&a); // Извлекаем из стека символ Out[l++] = a; // и записываем в строку Out

}

Op = InS(Op,In[k]); // Текущий символ – в стек

}

k++;

} // Конец цикла анализа входной строки

// Если стек не пуст, переписываем все операции в выходную строку

while (Op!=NULL) {

Op = OutS(Op,&a);

Out[l++] = a;

}

Out[l] = '\0’;

printf("\n Polish = %s", Out); // Выводим на экран результат

}

//======= Функция реализации приоритета операций =========

int Prior (char a) {

switch (a) {

case '*': case '/': return 3;

case '–': case '+': return 2;

case '(': return 1;

}

return 0;

}

// ============== Добавление элемента в стек =============

Stack* InS(Stack *t, char s) {

Stack *t1 = (Stack*) malloc(sizeof(Stack));

t1 -> c = s;

t1-> Next = t;

return t1;

}

// ============== Извлечение элемента из стека ===============

Stack* OutS(Stack *t, char *s) {

Stack *t1 = t;

*s = t -> c;

t = t->Next;

free(t1);

return t;

}


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.01 сек.)