Skip to main content

Упражнения: Shunting Yard Алгоритъм и Приложения на Stack/Queue

Напредък

0%
✅ Завършени: 0 / 0📊 Напредък: 0%

💡 Напредъкът се записва локално в браузъра

ℹ️Цел на Упражненията

Практически задачи за затвърдяване на знанията по:

  • Основни операции на Stack и Queue
  • Shunting Yard алгоритъм за конверсия от инфикс към RPN
  • Оценка на RPN изрази
  • Приоритет и асоциативност на операторите
  • C++ имплементация на парсери за изрази

Общо упражнения: 32 (8 лесни, 4 лесни-средни, 8 средни, 4 средни-трудни, 8 трудни)

Лесни Упражнения (Основни Концепции)​

10 minЛЕСНО

Задача 1: Последователност от Stack операции​

Задача: Дадена е следната последователност от операции върху празен стек: push(5), push(3), pop(), push(7), top(), pop(). Каква стойност връща операцията top()?

Проследете стека стъпка по стъпка след всяка операция:

  • След push(5): [5]
  • След push(3): [5, 3]
  • След pop(): [5]
  • И т.н.
✅Отговор: 7

Проследяване стъпка по стъпка:

ОперацияСъстояние на стекаВръщана стойност
push(5)[5]-
push(3)[5, 3]-
pop()[5]3
push(7)[5, 7]-
top()[5, 7]7
pop()[5]7

Операцията top() връща 7, тъй като това е елементът на върха на стека в този момент.

10 minЛЕСНО

Задача 2: LIFO подредба и Shunting Yard​

Задача: Обяснете със свои думи защо стекът използва LIFO (Last In, First Out) подредба и защо това свойство го прави подходящ за Shunting Yard алгоритъма.

✅LIFO и Shunting Yard

LIFO (Last In, First Out): Последният добавен елемент е първият, който се премахва.

Защо е подходящ за Shunting Yard:

  • При парсирането на изрази операторите трябва да се обработват в ред, базиран на техния приоритет
  • Операторите с по-висок приоритет (като *) трябва да "изчакат" до момента, в който всички операнди са налични
  • Стекът позволява временно съхранение на оператори и осигурява правилния ред на извличането им според приоритета
  • Когато срещнем оператор с по-нисък приоритет, трябва да "извадим" и обработим операторите с по-висок приоритет, които са отгоре в стека

Пример: При парсиране на 2 + 3 * 4:

  • + се натиска в стека
  • * има по-висок приоритет, затова се натиска след +
  • Когато израза приключи, първо се извлича *, след това + - точно в обратен ред на това как биха се изпълнили
10 minЛЕСНО

Задача 3: Подреждане на оператори по приоритет​

Задача: Подредете следните оператори от най-нисък към най-висок приоритет: ^, +, *, -, /

✅Подреждане по приоритет

От най-нисък към най-висок приоритет:

  1. Ниво 1 (най-нисък): +, - (събиране и изваждане)
  2. Ниво 2 (среден): *, / (умножение и деление)
  3. Ниво 3 (най-висок): ^ (степенуване)

Таблица:

ПриоритетОператориАсоциативност
1 (нисък)+, -Лява
2 (среден)*, /Лява
3 (висок)^Дясна
10 minЛЕСНО

Задача 4: Разпознаване на Инфиксна и RPN нотация​

Задача: Идентифицирайте кои от следните изрази са в инфиксна нотация и кои в RPN (постфиксна):

  • a) 3 + 4
  • b) 3 4 +
  • c) 5 2 * 3 +
  • d) (2 + 3) * 4
✅Класификация
ИзразТипОбяснение
a) 3 + 4ИнфикснаОператорът + е между операндите
b) 3 4 +RPN (Постфиксна)Операторът + е след операндите
c) 5 2 * 3 +RPN (Постфиксна)Операторите са след техните операнди
d) (2 + 3) * 4ИнфикснаОператорите са между операндите, със скоби

Забележка: В RPN не са нужни скоби, защото редът на операциите е вече определен от позицията на операторите.

10 minЛЕСНО

Задача 5: Стъпково изчисляване на RPN израз​

Задача: Изчислете RPN израза 5 3 + стъпка по стъпка, показвайки съдържанието на стека след всяка операция.

✅Стъпка по стъпка оценка

RPN Израз: 5 3 +

Процес:

СтъпкаТокенДействиеСтек
15Натискане на число[5]
23Натискане на число[5, 3]
3+Извличане на 3 и 5, изчисляване на 5 + 3 = 8, натискане на 8[8]

Краен резултат: 8

C++ код:

stack<int> st;
st.push(5);           // Стек: [5]
st.push(3);           // Стек: [5, 3]
int b = st.top(); st.pop();  // b = 3
int a = st.top(); st.pop();  // a = 5
st.push(a + b);       // Стек: [8]
return st.top();      // Резултат: 8
10 minЛЕСНО

Задача 6: Токенизация на математически израз​

Задача: Изброете всички токени в израза 12 + 34 * 5 в реда, в който ще бъдат обработени.

✅Списък на токените

Токени в ред:

  1. 12 (число)
  2. + (оператор)
  3. 34 (число)
  4. * (оператор)
  5. 5 (число)

Важни бележки:

  • 12 и 34 са многоцифрени числа, не отделни цифри
  • Интервалите между токените се игнорират
  • Токените се обработват отляво надясно
10 minЛЕСНО

Задача 7: Лява и дясна асоциативност​

Задача: Каква е разликата между ляво-асоциативни и дясно-асоциативни оператори? Дайте по един пример за всеки от лекцията.

✅Асоциативност на операторите

Лява асоциативност

Операторите се оценяват отляво надясно

Примери: +, -, *, /

10 - 3 - 2
= (10 - 3) - 2
= 7 - 2
= 5

Дясна асоциативност

Операторите се оценяват отдясно наляво

Пример: ^ (степенуване)

2 ^ 3 ^ 2
= 2 ^ (3 ^ 2)
= 2 ^ 9
= 512

Защо е важно: Асоциативността определя реда на операциите когато имаме множество оператори с еднакъв приоритет. Shunting Yard алгоритъмът трябва да зачита асоциативността при извличането на оператори от стека.

10 minЛЕСНО

Задача 8: Роля на скобите в математически изрази​

Задача: Защо изразът 2 + 3 * 4 се изчислява на 14, но (2 + 3) * 4 се изчислява на 20? Обяснете ролята на скобите.

✅Скоби и приоритет

Без скоби: 2 + 3 * 4

Приоритет на операторите:

  • * има по-висок приоритет от +
  • Оценка: 2 + (3 * 4) = 2 + 12 = 14

RPN: 2 3 4 * +

Със скоби: (2 + 3) * 4

Скобите заместват приоритета:

  • Изразът в скобите се оценява първи
  • Оценка: (2 + 3) * 4 = 5 * 4 = 20

RPN: 2 3 + 4 *

Роля на скобите:

  • Скобите временно заместват правилата за приоритет по подразбиране
  • Принудават израза вътре да се оценява първи, независимо от приоритета
  • В RPN скобите не са необходими, защото редът вече е определен

Лесни-Средни Упражнения (Приложение на Основни Концепции)​

15 minСРЕДНО

Задача 9: Проста конверсия от инфикс към RPN​

Задача: Конвертирайте инфиксния израз A + B в RPN нотация. Покажете работата си стъпка по стъпка със състоянията на стека и изходната опашка.

✅Конверсия стъпка по стъпка

Инфикс: A + B

Процес:

СтъпкаТокенСтекИзходна опашкаДействие
1A[][A]Число → изход
2+[+][A]Оператор → стек
3B[+][A, B]Число → изход
Край-[][A, B, +]Изпразване на стека

RPN Резултат: A B +

15 minСРЕДНО

Задача 10: RPN изчисляване с множество операции​

Задача: Изчислете RPN израза 2 3 + 4 *, показвайки състоянието на стека след обработката на всеки токен.

✅Пълно проследяване

RPN Израз: 2 3 + 4 *

СтъпкаТокенТипДействиеСтек
12ЧислоPush 2[2]
23ЧислоPush 3[2, 3]
3+ОператорPop 3 и 2, изчисли 2+3=5, push 5[5]
44ЧислоPush 4[5, 4]
5*ОператорPop 4 и 5, изчисли 5*4=20, push 20[20]

Краен резултат: 20

Съответният инфиксен израз: (2 + 3) * 4 = 5 * 4 = 20

15 minСРЕДНО

Задача 11: Приоритет на операторите в действие​

Задача: Конвертирайте инфиксния израз 2 + 3 * 4 в RPN. Обяснете защо операторът за умножение се обработва преди събирането.

✅Конверсия с приоритет

Инфикс: 2 + 3 * 4

Процес:

СтъпкаТокенСтекИзходна опашкаОбяснение
12[][2]Число → изход
2+[+][2]Оператор → стек
33[+][2, 3]Число → изход
4*[+, *][2, 3]* има по-висок приоритет от +, затова се натиска
54[+, *][2, 3, 4]Число → изход
Край-[][2, 3, 4, *, +]Изпразване: първо *, след това +

RPN Резултат: 2 3 4 * +

Обяснение:

  • * има приоритет 2, + има приоритет 1
  • Когато срещнем *, той не изважда + от стека, защото има по-висок приоритет
  • В края първо се извлича * (по-висок приоритет), след това +
  • Това осигурява, че умножението се извършва преди събирането
15 minСРЕДНО

Задача 12: Проследяване на последователност от stack операции​

Задача: Дадени са операциите push(10), push(20), push(30), pop(), top(). Какво е крайното състояние на стека и каква стойност връща top()?

✅Проследяване
ОперацияСтек след операциятаВръщана стойност
push(10)[10]-
push(20)[10, 20]-
push(30)[10, 20, 30]-
pop()[10, 20]30
top()[10, 20]20

Крайно състояние на стека: [10, 20] (с 20 на върха)

Стойност, върната от top(): 20

Средни Упражнения (Междинно Решаване на Проблеми)​

15 minСРЕДНО

Задача 13: Конверсия с използване на скоби​

Задача: Конвертирайте инфиксния израз (A + B) * C в RPN нотация. Покажете стека с оператори и изходната опашка на всяка стъпка.

✅Конверсия със скоби

Инфикс: (A + B) * C

СтъпкаТокенСтекИзходна опашкаОбяснение
1([(][]Лява скоба → стек
2A[(][A]Число → изход
3+[(, +][A]Оператор → стек
4B[(, +][A, B]Число → изход
5)[][A, B, +]Дясна скоба → изваждане до (
6*[*][A, B, +]Оператор → стек
7C[*][A, B, +, C]Число → изход
Край-[][A, B, +, C, *]Изпразване на стека

RPN Резултат: A B + C *

Оценка: Първо събираме A и B, след това умножаваме резултата по C.

15 minСРЕДНО

Задача 14: Израз с множество различни оператори​

Задача: Конвертирайте A + B * C - D в RPN. Покажете всички междинни стъпки със съдържанието на стека и опашката.

✅Пълно проследяване

Инфикс: A + B * C - D

СтъпкаТокенСтекИзходна опашкаОбяснение
1A[][A]Число → изход
2+[+][A]Оператор → стек
3B[+][A, B]Число → изход
4*[+, *][A, B]* (приоритет 2) > + (приоритет 1) → стек
5C[+, *][A, B, C]Число → изход
6-[-][A, B, C, *, +]- (приоритет 1) ≤ * (приоритет 2) → изваждане на * и +, натискане на -
7D[-][A, B, C, *, +, D]Число → изход
Край-[][A, B, C, *, +, D, -]Изпразване на стека

RPN Резултат: A B C * + D -

Оценка: A + (B * C) - D

15 minСРЕДНО

Задача 15: Дясна асоциативност и степенуване​

Задача: Конвертирайте 10 - 3 - 2 в RPN, след това го изчислете. Обяснете как лявата асоциативност влияе на резултата (сравнете с това какво би се случило, ако изваждането беше дясно-асоциативно).

✅Лява vs Дясна асоциативност

Инфикс: 10 - 3 - 2

С лява асоциативност (правилно):

ТокенСтекИзход
10[][10]
-[-][10]
3[-][10, 3]
-[-][10, 3, -, 2] → Извлича първия -
2[-][10, 3, -, 2]
Край[][10, 3, -, 2, -]

RPN (лява асоциативност): 10 3 - 2 - Оценка: (10 - 3) - 2 = 7 - 2 = 5

Ако беше дясно-асоциативно (хипотетично): RPN: 10 3 2 - - Оценка: 10 - (3 - 2) = 10 - 1 = 9

Лява асоциативност (правилно)

10 - 3 - 2
= (10 - 3) - 2
= 7 - 2
= 5

Дясна асоциативност (грешно за -)

10 - 3 - 2
= 10 - (3 - 2)
= 10 - 1
= 9

Заключение: Лявата асоциативност е критична за коректното изчисляване на изваждане и деление.

15 minСРЕДНО

Задача 16: RPN изчисляване с операция деление​

Задача: Изчислете RPN израза 15 3 / 2 +, показвайки всяка стъпка. Какъв е крайният резултат?

✅Стъпка по стъпка

RPN Израз: 15 3 / 2 +

СтъпкаТокенДействиеСтек
115Push 15[15]
23Push 3[15, 3]
3/Pop 3 и 15, изчисли 15/3=5, push 5[5]
42Push 2[5, 2]
5+Pop 2 и 5, изчисли 5+2=7, push 7[7]

Краен резултат: 7

Еквивалентен инфиксен израз: (15 / 3) + 2 = 5 + 2 = 7

20 minТРУДНО

Задача 17: Откриване на грешки при RPN изчисляване​

Задача: Идентифицирайте какво не е наред със следния RPN израз: 3 + 4 5 *. Как бихте го поправили?

⚠️Грешка в израза

Проблем: 3 + 4 5 * не е валиден RPN израз!

Анализ:

  • В RPN всички оператори трябва да идват след техните операнди
  • + се появява преди да има два операнда за обработка

Опит за оценка:

  1. 3 → Push 3 → Стек: [3]
  2. + → ГРЕШКА! Нужни са 2 операнда, но в стека има само 1

Какво може би се е имало предвид:

Вариант 1: 3 4 5 * +

Оценка: 3 + (4 * 5) = 3 + 20 = 23

Инфикс: 3 + 4 * 5

Вариант 2: 3 4 + 5 *

Оценка: (3 + 4) * 5 = 7 * 5 = 35

Инфикс: (3 + 4) * 5

20 minТРУДНО

Задача 18: Конверсия на израз с вложени скоби​

Задача: Конвертирайте инфиксния израз ((A + B) * C) в RPN. Проследете алгоритъма, показвайки как се обработват вложените скоби.

✅Обработка на вложени скоби

Инфикс: ((A + B) * C)

СтъпкаТокенСтекИзходОбяснение
1([(][]Лява скоба 1 → стек
2([(, (][]Лява скоба 2 → стек
3A[(, (][A]Число → изход
4+[(, (, +][A]Оператор → стек
5B[(, (, +][A, B]Число → изход
6)[(][A, B, +]Дясна скоба → изваждане до вътрешна (
7*[(, *][A, B, +]Оператор → стек
8C[(, *][A, B, +, C]Число → изход
9)[][A, B, +, C, *]Дясна скоба → изваждане до външна (

RPN Резултат: A B + C *

Ключови наблюдения:

  • Всяка лява скоба ( се натиска в стека и действа като маркер
  • Всяка дясна скоба ) инициира изваждане до съответната лява скоба
  • Скобите не се включват в крайния RPN изход
20 minТРУДНО

Задача 19: Степенуване с дясна асоциативност​

Задача: Конвертирайте 2 ^ 3 ^ 2 в RPN, правилно обработвайки дясната асоциативност на степенуването. След това изчислете RPN израза.

✅Дясна асоциативност на ^

Инфикс: 2 ^ 3 ^ 2

Конверсия в RPN:

СтъпкаТокенСтекИзходОбяснение
12[][2]Число → изход
2^[^][2]Оператор → стек
33[^][2, 3]Число → изход
4^[^, ^][2, 3]Дясна асоциативност: не извличаме предишния ^
52[^, ^][2, 3, 2]Число → изход
Край-[][2, 3, 2, ^, ^]Изпразване: отдясно наляво

RPN Резултат: 2 3 2 ^ ^

Оценка на RPN:

СтъпкаТокенДействиеСтек
12Push[2]
23Push[2, 3]
32Push[2, 3, 2]
4^Pop 2,3 → 3^2=9, push[2, 9]
5^Pop 9,2 → 2^9=512, push[512]

Краен резултат: 512

Важно: 2 ^ 3 ^ 2 = 2 ^ (3 ^ 2) = 2 ^ 9 = 512, НЕ (2 ^ 3) ^ 2 = 8 ^ 2 = 64

20 minТРУДНО

Задача 20: Смесен приоритет на оператори​

Задача: Конвертирайте инфиксния израз A * B + C / D в RPN. Покажете как се обработват операторите с еднакъв приоритет.

✅Еднакъв приоритет

Инфикс: A * B + C / D

СтъпкаТокенСтекИзходОбяснение
1A[][A]Число → изход
2*[*][A]Оператор → стек
3B[*][A, B]Число → изход
4+[+][A, B, *]+ (приоритет 1) < * (приоритет 2) → извличане на *
5C[+][A, B, *, C]Число → изход
6/[+, /][A, B, *, C]/ (приоритет 2) > + (приоритет 1) → натискане
7D[+, /][A, B, *, C, D]Число → изход
Край-[][A, B, *, C, D, /, +]Изпразване: първо /, след това +

RPN Резултат: A B * C D / +

Оценка: (A * B) + (C / D)

Ключови точки:

  • * и / имат еднакъв приоритет (2), но се обработват отляво надясно (лява асоциативност)
  • + има по-нисък приоритет (1) и се изпълнява последен

Средни-Трудни Упражнения (Сложни Приложения)​

20 minТРУДНО

Задача 21: Конверсия на сложен израз​

Задача: Конвертирайте инфиксния израз 3 + 4 * 2 / (1 - 5) в RPN. Покажете пълни проследявания на стека с оператори и изходната опашка.

✅Пълна конверсия

Инфикс: 3 + 4 * 2 / (1 - 5)

СтъпкаТокенСтекИзходОбяснение
13[][3]Число
2+[+][3]Оператор
34[+][3, 4]Число
4*[+, *][3, 4]По-висок приоритет
52[+, *][3, 4, 2]Число
6/[+, /][3, 4, 2, *]Еднакъв приоритет с *, лява асоциативност
7([+, /, (][3, 4, 2, *]Лява скоба
81[+, /, (][3, 4, 2, *, 1]Число
9-[+, /, (, -][3, 4, 2, *, 1]Оператор
105[+, /, (, -][3, 4, 2, *, 1, 5]Число
11)[+, /][3, 4, 2, *, 1, 5, -]Дясна скоба: извличане до (
Край-[][3, 4, 2, *, 1, 5, -, /, +]Изпразване

RPN Резултат: 3 4 2 * 1 5 - / +

Оценка:

= 3 + ((4 * 2) / (1 - 5))
= 3 + (8 / (-4))
= 3 + (-2)
= 1
20 minТРУДНО

Задача 22: Идентификация на унарен оператор​

Задача: В израза -3 + 4 * -5, идентифицирайте кои знаци за минус са унарни и кои са бинарни. Обяснете как сте определили това.

✅Унарни vs Бинарни оператори

Израз: -3 + 4 * -5

Анализ:

Първи минус: -3

Тип: УНАРЕН

Защо:

  • Появява се в началото на израза
  • Няма лев операнд
  • Отрицание на числото 3

Плюс: +

Тип: БИНАРЕН

Защо:

  • Има лев операнд (-3)
  • Има десен операнд (резултатът от 4 * -5)

Умножение: *

Тип: БИНАРЕН

Защо:

  • Има лев операнд (4)
  • Има десен операнд (-5)

Втори минус: -5

Тип: УНАРЕН

Защо:

  • Появява се след оператор *
  • Няма непосредствен лев операнд
  • Отрицание на числото 5

Правила за разпознаване на унарен минус:

  1. В началото на израза: -3
  2. След лява скоба: (-5)
  3. След оператор: 4 * -5

Токенизация:

  • -3 → Токен: -3 (унарно отрицателно число) или u 3 (унарен оператор + число)
  • + → Токен: + (бинарен оператор)
  • 4 → Токен: 4 (число)
  • * → Токен: * (бинарен оператор)
  • -5 → Токен: -5 (унарно отрицателно число) или u 5 (унарен оператор + число)

RPN с унарен оператор 'u': 3 u 4 5 u * +

20 minТРУДНО

Задача 23: Симулация на алгоритъма​

Задача: Дадени израз A + B * C + D, ръчно симулирайте Shunting Yard алгоритъма. Създайте таблица, показваща: Текущ токен | Стек с оператори | Изходна опашка за всяка стъпка.

✅Пълна симулация

Инфикс: A + B * C + D

СтъпкаТекущ токенСтек с операториИзходна опашкаОписание на действието
1A[][A]Операнд → директно към изхода
2+[+][A]Оператор с приоритет 1 → стек
3B[+][A, B]Операнд → директно към изхода
4*[+, *][A, B]* (приоритет 2) > + (приоритет 1) → стек
5C[+, *][A, B, C]Операнд → директно към изхода
6+[+][A, B, C, *, +]Нов +: извличане на * (по-висок), извличане на стар + (еднакъв, лява асоциативност), натискане на нов +
7D[+][A, B, C, *, +, D]Операнд → директно към изхода
Край-[][A, B, C, *, +, D, +]Изпразване на всички оператори от стека

RPN Резултат: A B C * + D +

Оценка: (A + (B * C)) + D

Ключови моменти:

  • Стъпка 6 е критична: когато срещнем втория +, трябва да извадим всички оператори с по-висок или равен приоритет
  • След това натискаме новия + в стека
20 minТРУДНО

Задача 24: Изчисляване с проверка за грешки​

Задача: Напишете псевдокод за RPN изчислител, който включва проверка за грешки при недостатъчни операнди и невалидни изрази.

✅Псевдокод с проверка за грешки
RPN Evaluator with Error Checking
double evaluateRPN(vector<string> tokens) {
    stack<double> operandStack;

    for (token in tokens) {
        if (isNumber(token)) {
            // Конвертирай и натисни числото
            operandStack.push(stringToDouble(token));
        }
        else if (isBinaryOperator(token)) {
            // Проверка: нужни са поне 2 операнда
            if (operandStack.size() < 2) {
                throw Error("Недостатъчно операнди за оператор " + token);
            }

            // Извличане на операндите (обърнат ред!)
            double rightOperand = operandStack.top();
            operandStack.pop();
            double leftOperand = operandStack.top();
            operandStack.pop();

            // Проверка за деление на нула
            if (token == "/" && rightOperand == 0) {
                throw Error("Деление на нула");
            }

            // Изчисляване на резултата
            double result = applyBinaryOperator(token, leftOperand, rightOperand);
            operandStack.push(result);
        }
        else if (isUnaryOperator(token)) {
            // Проверка: нужен е поне 1 операнд
            if (operandStack.size() < 1) {
                throw Error("Недостатъчно операнди за унарен оператор " + token);
            }

            double operand = operandStack.top();
            operandStack.pop();
            double result = applyUnaryOperator(token, operand);
            operandStack.push(result);
        }
        else {
            throw Error("Невалиден токен: " + token);
        }
    }

    // Проверка: стекът трябва да съдържа точно 1 резултат
    if (operandStack.size() != 1) {
        throw Error("Невалиден израз: " +
                    toString(operandStack.size()) +
                    " операнди остават в стека");
    }

    return operandStack.top();
}

Проверки за грешки:

  1. Недостатъчно операнди за бинарен оператор (нужни 2)
  2. Недостатъчно операнди за унарен оператор (нужен 1)
  3. Деление на нула
  4. Невалиден токен
  5. След оценката: стекът трябва да има точно 1 елемент

Трудни Упражнения (Напреднало Решаване на Проблеми)​

20 minТРУДНО

Задача 25: Класическият пример от Wikipedia​

Задача: Конвертирайте пълния израз 3 + 4 * 2 / (1 - 5) ^ 2 ^ 3 в RPN, следвайки всички правила за приоритет, асоциативност и скоби. След това изчислете RPN израза, за да получите крайния числен резултат.

Обърнете специално внимание на дясната асоциативност на степенуването (^). Когато виждате 2 ^ 3, не извличайте предишен ^ от стека.

✅Пълно решение - Wikipedia Example

Инфикс: 3 + 4 * 2 / (1 - 5) ^ 2 ^ 3

Задача 26: Част 1: Конверсия в RPN​

СтъпкаТокенСтекИзход
13[][3]
2+[+][3]
34[+][3, 4]
4*[+, *][3, 4]
52[+, *][3, 4, 2]
6/[+, /][3, 4, 2, *]
7([+, /, (][3, 4, 2, *]
81[+, /, (][3, 4, 2, *, 1]
9-[+, /, (, -][3, 4, 2, *, 1]
105[+, /, (, -][3, 4, 2, *, 1, 5]
11)[+, /][3, 4, 2, *, 1, 5, -]
12^[+, /, ^][3, 4, 2, *, 1, 5, -]
132[+, /, ^][3, 4, 2, *, 1, 5, -, 2]
14^[+, /, ^, ^][3, 4, 2, *, 1, 5, -, 2]
153[+, /, ^, ^][3, 4, 2, *, 1, 5, -, 2, 3]
Край-[][3, 4, 2, *, 1, 5, -, 2, 3, ^, ^, /, +]

RPN Резултат: 3 4 2 * 1 5 - 2 3 ^ ^ / +

Задача 27: Част 2: Оценка на RPN​

СтъпкаТокенДействиеСтек
13Push[3]
24Push[3, 4]
32Push[3, 4, 2]
4*Pop 2,4 → 4*2=8[3, 8]
51Push[3, 8, 1]
65Push[3, 8, 1, 5]
7-Pop 5,1 → 1-5=-4[3, 8, -4]
82Push[3, 8, -4, 2]
93Push[3, 8, -4, 2, 3]
10^Pop 3,2 → 2^3=8[3, 8, -4, 8]
11^Pop 8,-4 → (-4)^8=65536[3, 8, 65536]
12/Pop 65536,8 → 8/65536=0.0001220703125[3, 0.0001220703125]
13+Pop 0.000122...,3 → 3+0.000122=3.0001220703125[3.0001220703125]

Краен резултат: 3.0001220703125 (или приблизително 3.000122)

Задача 28: Ключови точки:​

  • Дясна асоциативност: 2 ^ 3 ^ 2 стана 2 3 ^ в RPN първо
  • Отрицателно степенуване: (-4) ^ 8 = 65536 (четна степен → положителен резултат)
  • Порядък на операциите: Умножение и деление преди събиране
20 minТРУДНО

Задача 29: Напреднали теми за самостоятелна работа​

ℹ️Напреднали упражнения

Останалите упражнения (26-32) изискват по-задълбочени имплементации и дизайнерски решения:

Упражнение 26: Обработка на унарни оператори - дизайн на модификация за -3 * (4 + -5)

Упражнение 27: C++ имплементация дизайн - сигнатура и подход за infixToRPN()

Упражнение 28: Дебъгване - идентифициране на грешка в студентска имплементация

Упражнение 29: Имплементация на дясна асоциативност - модификация на shouldPop()

Упражнение 30: Сложен вложен израз - ((15 / (7 - (1 + 1))) * 3) - (2 + (1 + 1))

Упражнение 31: Дизайн на разширение за функции - sin(30), max(3, 5, 7)

Упражнение 32: Цялостна имплементация - пълен C++ клас ExpressionParser

⚠️Препоръка

Тези напреднали упражнения са подходящи за самостоятелна работа или проектни задачи. Те изискват комбиниране на всички наученидо момента концепции и добро разбиране на C++ имплементация.

За пълни решения на тези упражнения, консултирайте се с преподавателя или проучете допълнителните ресурси в лекцията.

Обобщение​

✅Какво научихте

Чрез тези 32 упражнения вие:

  • Овладяхте основните операции на Stack и Queue
  • Разбрахте и приложихте Shunting Yard алгоритъма
  • Научихте да конвертирате инфиксни изрази в RPN
  • Можете да оценявате RPN изрази коректно
  • Разбирате приоритета и асоциативността на операторите
  • Готови сте да имплементирате парсери за изрази в C++
ℹ️Следващи стъпки
  1. Имплементирайте пълен калкулатор с всички функции
  2. Добавете поддръжка за променливи (x, y)
  3. Разширете с математически функции (sin, cos, sqrt)
  4. Създайте графичен интерфейс за вашия калкулатор
  5. Проучете как компилаторите използват подобни техники