Приложения на Stack и Queue: Shunting Yard Алгоритъм, Изчисляване на Изрази и Reverse Polish Notation
▶⚡ Накратко
За Изпита🎯Учебни Цели
След края на тази лекция вие ще можете да:
- ✓Обяснете структурите от данни stack и queue и техните приложения
- ✓Разберете целта и методологията на Shunting Yard алгоритъма
- ✓Парсирайте и изчислявайте математически изрази
- ✓Имплементирайте Shunting Yard алгоритъма в C++
- ✓Управлявайте приоритета на операторите, асоциативността и скобите
1. Въведение и Мотивация за Парсиране на Изрази
Парсирането на изрази е краеугълен камък в компютърните науки и програмирането. Хората използват инфиксна нотация (напр. 2 + 3 * 4) интуитивно, разбирайки правилата за приоритет на операторите ("умножението преди събирането") почти несъзнателно. Въпреки това, компютрите изискват явни, структурирани алгоритми, за да определят правилния ред на операциите, защото обработват изразите линейно, по един токен наведнъж, и нямат вродено знание за математически конвенции.
Защо е необходимо парсирането?
Наивна оценка
Лява към дясна: 2 + 3 * 4 дава (2 + 3) * 4 = 20
❌ Грешно! Игнорира приоритета на операторите.
Правилна оценка
С приоритет: 2 + 3 * 4 дава 2 + (3 * 4) = 14
✅ Правилно! Умножението се изпълнява първо.
Ако парсирането на изрази не съществуваше, потребителите щяха да трябва да добавят скоби навсякъде, за да осигурят коректност, което прави софтуера неприятелски настроен и податлив на грешки.
Инфиксна vs. Reverse Polish Notation (RPN)
Инфиксна нотация
- Оператори между операндите: A + B
- Човешки приятелска
- Двусмислена без приоритет или скоби
- Изисква сложен парсинг
Reverse Polish Notation (RPN)
- Оператори след операндите: A B +
- Машинно приятелска
- Няма нужда от скоби или правила за приоритет
- Оценката е тривиална отляво надясно
RPN е перфектно подходяща за компютрите, защото оценката на израза може да се извърши отляво надясно използвайки стек, елиминирайки двусмислеността и опростявайки имплементацията.
Приложения в реалния свят
Компилатори
Всеки компилатор използва парсиране на изрази за генериране на машинен код от if (a > b + 1).
Калкулатори
Вашият калкулатор използва подобни алгоритми за оценка на изрази.
Електронни таблици
Excel изчислява =A1 + B2 * C3 използвайки парсиране на изрази.
Здравото парсиране на изрази е незаменимо за коректност и използваемост във всички тези приложения.
2. Преговор: Основи на Stack и Queue
Разбирането на стековете и опашките е фундаментално за Shunting Yard алгоритъма и оценката на изрази.
2.1. Stack операции (Push, Pop, Peek) – LIFO
Stack (Стек) е структура от данни, която следва принципа LIFO (Last In, First Out) - последният добавен елемент е първият, който се премахва.
Основни операции:
- Push: Добавя елемент на върха
- Pop: Премахва върха на елемента
- Peek/Top: Разглежда върха без да го премахва
#include <stack>
std::stack<int> s;
s.push(4);
s.push(2);
s.push(7);
int t = s.top(); // 7
s.pop(); // Премахва 7
// Сега top е 2
Stack управлява временно съхранени оператори и проследява вложени или чакащи операции.
2.2. Queue операции (Enqueue, Dequeue) – FIFO
Queue (Опашка) е структура от данни, която следва принципа FIFO (First In, First Out) - първият добавен елемент е първият, който се премахва.
Основни операции:
- Enqueue/Push: Добавя елемент на края
- Dequeue/Pop: Премахва елемент от началото
- Peek/Front: Разглежда предния елемент
#include <queue>
std::queue<int> q;
q.push(10);
q.push(20);
q.push(30);
int f = q.front(); // 10
q.pop(); // Премахва 10
// Сега front е 20
Queue (често имплементирана с std::deque) събира токени за крайната изходна последователност.
2.3. Приоритет и Асоциативност на Операторите
- Приоритет: Умножение/деление > събиране/изваждане; степенуването е най-високо
- Асоциативност: Повечето оператори са ляво-асоциативни (оценка отляво надясно); степенуването е дясно-асоциативно
Примери:
Лява асоциативност
10 - 3 - 2
→ (10 - 3) - 2 = 5
Дясна асоциативност
2 ^ 3 ^ 2
→ 2 ^ (3 ^ 2) = 512
не (2 ^ 3) ^ 2 = 64
Скобите позволяват временно заместване на правилата по подразбиране и имат най-висок приоритет.
3. Shunting Yard Алгоритъм: Основни Концепции
3.1. Преглед на алгоритъма
Разработен от Edsger Dijkstra през 1961 г., Shunting Yard алгоритъмът конвертира инфиксни изрази (напр. 3 + 4 * 2) в RPN (напр. 3 4 2 * +). Това прави оценката тривиална за компютрите.
3.2. Токенизация: Разбиване на израза
Преди обработката входният низ се токенизира на числа, оператори и скоби.
std::vector<std::string> tokenize(const std::string& expr) {
// Използвайте std::istringstream или парсиране символ по символ
// за обработка на интервали, многоцифрени числа, десетични и др.
// ...
}
- Многоцифрени числа:
123,45.67 - Оператори:
+,-,*,/,^ - Скоби:
(,) - Интервали (които трябва да се игнорират)
3.3. Основен Алгоритмичен Поток
Алгоритъмът поддържа:
- Operator Stack: Временно съхранява оператори и скоби
- Output Queue: Събира получените RPN токени
- Операнд (Число): Натиснете директно към изходната опашка
- Оператор:
- Докато върхът на стека има по-висок (или равен и ляво-асоциативен) приоритет, извадете от стека към опашката
- Натиснете входящия оператор в стека
- Лява скоба
(: Натиснете в стека (като маркер) - Дясна скоба
): Извадете от стека към опашката докато не се намери съответстваща((изхвърлете и двете скоби) - В края: Извадете всички останали оператори от стека към изходната опашка
3.4. Таблица за Приоритет на Операторите
| Оператор | Приоритет | Асоциативност |
|---|---|---|
+, - | 1 | Лява |
*, / | 2 | Лява |
^ | 3 | Дясна |
3.5. Пример за проследяване
Инфикс: 3 + 4 * 2
RPN: 3 4 2 * +
Стъпки:
| Токен | Стек | Изходна опашка |
|---|---|---|
3 | [] | [3] |
+ | [+] | [3] |
4 | [+] | [3, 4] |
* | [+, *] | [3, 4] |
2 | [+, *] | [3, 4, 2] |
| Край | [] | [3, 4, 2, *, +] |
Резултат: 3 4 2 * +
3.6. C++ Скелет
std::vector<std::string> infixToRPN(const std::string& expr) {
std::vector<std::string> tokens = tokenize(expr);
std::stack<std::string> opStack;
std::vector<std::string> output;
for (const auto& token : tokens) {
if (isNumber(token)) {
output.push_back(token);
}
else if (isOperator(token)) {
while (!opStack.empty() && shouldPop(opStack.top(), token)) {
output.push_back(opStack.top());
opStack.pop();
}
opStack.push(token);
}
else if (token == "(") {
opStack.push(token);
}
else if (token == ")") {
while (opStack.top() != "(") {
output.push_back(opStack.top());
opStack.pop();
}
opStack.pop(); // Премахнете '('
}
}
// Извадете останалите оператори
while (!opStack.empty()) {
output.push_back(opStack.top());
opStack.pop();
}
return output;
}
4. Конверсия: От Инфикс към RPN
4.1. Прост пример
Инфикс: 2 + 5 * 3 / 2
RPN: 2 5 3 * 2 / +
Процес:
- Натиснете числата към изхода
*и/имат по-висок приоритет; обработват се преди+- Оценете като
2 + ((5 * 3) / 2)=2 + (15 / 2)=9.5
4.2. Сложен пример: Дясна асоциативност
Инфикс: 2 ^ 3 ^ 2
RPN: 2 3 2 ^ ^
Процес:
- Степенуването е дясно-асоциативно
- Оценете като
2 ^ (3 ^ 2)=2 ^ 9=512 - Не
(2 ^ 3) ^ 2=8 ^ 2=64
4.3. Сложен пример със скоби
Инфикс: (4 + 3 * 20) / (10 + 3 * 3 ^ 2 - 12)
Скобите създават изолирани подизрази. Проследете стъпка по стъпка, обновявайки стека и опашката както е описано.
5. Оценка: Изчисляване на резултати от RPN
5.1. RPN (Postfix) Алгоритъм за оценка
За всеки токен:
- Ако е число, натиснете към стека
- Ако е оператор, извадете необходимите операнди от стека, приложете оператора, натиснете резултата обратно
В края стекът съдържа точно едно число—отговорът
double evaluateRPN(const std::vector<std::string>& rpn) {
std::stack<double> st;
for (const auto& token : rpn) {
if (isNumber(token)) {
st.push(std::stod(token));
} else {
double b = st.top(); st.pop();
double a = st.top(); st.pop();
st.push(applyOperator(token, a, b));
}
}
return st.top();
}
Тъй като редът на RPN е явен, операторите винаги намират правилните си операнди. Няма нужда да разбирате приоритета или асоциативността по време на оценката!
5.2. Проверка за грешки
- Недостатъчни операнди в стека? Изразът е лошо форматиран
- Стекът има повече от една стойност в края? Твърде много операнди, недостатъчно оператори
- Деление на нула: Проверете преди прилагане на оператора
6. C++ Имплементация: Преглед
6.1. Структури от данни
std::vector<std::string> // Съхранение на токени
std::stack<std::string> // Стек с оператори
std::deque<std::string> // Изходна опашка (или vector)
6.2. Представяне на токени
enum class TokenType { Number, Operator, LeftParen, RightParen };
struct Token {
TokenType type;
std::string str;
bool isUnary = false;
};
6.3. Таблица за приоритет
std::map<char, int> precedence = {
{'+', 1}, {'-', 1},
{'*', 2}, {'/', 2},
{'^', 3}
};
std::map<char, bool> rightAssoc = {
{'^', true},
{'+', false}, {'-', false},
{'*', false}, {'/', false}
};
7. Обработка на Унарни Оператори и Напреднали Случаи
7.1. Разграничаване на унарен от бинарен минус
- В началото:
-3 - След '(':
(-4 + 2) - След оператор:
2 * -5
Използвайте специален токен (напр. u) за унарен минус с най-висок приоритет, дясно-асоциативен.
7.2. Оценка на унарни оператори
if (isUnaryOperator(token)) {
double a = st.top(); st.pop();
st.push(-a); // За унарен минус
}
7.3. Разширение до функции
Третирайте ги като унарни оператори с персонализиран приоритет или обработвайте като специални функционални токени. Това е напреднало разширение за по-пълни парсери.
8. Примери и Казуси
8.1. Класическият пример от Wikipedia
Инфикс: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
Стъпки:
- Токенизирайте входа
- Конвертирайте в RPN използвайки алгоритъма
- Оценете RPN използвайки стек
Проверки:
- Умножение/деление преди събиране
- Степенуването дясно-асоциативно
- Скобите заместват приоритета
8.2. Идея за графичен калкулатор
// Парсирайте f(x) = x^2 + 3
// За всяко x, заменете стойността, оценете RPN и начертайте (x, y)
8.3. Modulo и Floating-Point аритметика
- Modulo (
%): Само за цели числа в C++ - Floating-point оценка:
2.5 + 0.1може да има грешки при закръгляване; сравнявайте използвайки epsilon при тестване
9. Дейности и Ангажиране на Студентите
9.1. Think-Pair-Share: Стратегии за токенизация
Мисли
Всеки студент обмисля как да токенизира -3.14 + 2 * (5 - 1)
Сдвои се
Обсъдете компромисите (простота, гранични случаи)
Сподели
Представете стратегии на класа
9.2. Ръководена практика: Ръчно проследяване
В малки групи проследете 2 + 3 * 4 използвайки стек и опашка на хартия. Взаимно проверявайте отговорите.
9.3. Бърз тест
- Конвертирайте
A * B + Cв RPN - Обяснете защо умножението идва преди събирането
- Какво трябва да съдържа стекът след обработката на
*вA * B + C?
10. Обобщение и Ключови Изводи
- Shunting Yard алгоритъмът свързва човешки четим инфикс и машинно приятелски постфикс (RPN)
- Приоритетът и асоциативността на операторите са от съществено значение - алгоритъмът използва явно сравнение за налагане на правилния ред на оценка
- Stack и queue абстракциите са мощни инструменти за решаване на проблеми - този урок предоставя конкретен, мотивиращ пример
- C++ имплементациите изискват внимание към структурите от данни и обработката на грешки
11. Разширения и По-нататъшно Обучение
Променливи и функции
Разширете токенизацията и парсирането, за да поддържате променливи (x, y) и извиквания на функции (sin(x), max(1,2,3))
AST Construction
Конвертирайте Shunting Yard алгоритъма, за да произведе Abstract Syntax Tree за използване в компилатори
По-нататъшно изучаване:
- Имплементирайте пълнофункционален калкулатор с променливи и функции
- Проучете как Shunting Yard се вписва във front-end на съвременните езици за програмиране
- Изследвайте как компилаторите използват AST за оптимизация и генериране на код
Референции:
- Wikipedia: Shunting Yard Algorithm
- Dijkstra, E.W., "An Algol Compiler for the x1"
- GeeksforGeeks: Shunting Yard
- Compilers: Principles, Techniques, and Tools (Aho, Lam, Sethi, Ullman)
- C++ Reference: std::stack, std::queue, std::deque
Заключение
Shunting Yard алгоритъмът е елегантен и мощен инструмент за парсиране на изрази. Разбирането на това как работи не само подобрява вашите умения за решаване на проблеми, но и ви подготвя за по-напреднали теми в компилаторите, интерпретаторите и парсирането на езици.
- Как да конвертирате инфиксни изрази в RPN
- Как да оценявате RPN изрази използвайки стек
- Как да обработвате приоритет, асоциативност и скоби
- Как да имплементирате парсер за изрази в C++
Допълнителни Ресурси
Stack и Queue Приложения
- Stack and Queue Problems - GeeksforGeeks - Практически задачи
- 25 Stack, Queue, LinkedList Problems - LeetCode колекция
- Mastering Stack and Queue Problems - Comprehensive guide
Expression Parsing
- Shunting Yard Algorithm - Wikipedia обяснение
- Infix to Postfix Conversion - Стъпка по стъпка
- Expression Evaluation using Stack - С примери
Интервюни Въпроси
- Top 30 Stack and Queue Interview Questions - За подготовка
- Stacks & Queues Interview Questions - Концепции и приложения
- Stack Coding Problems for Interviews - Top 50 задачи
Реални Приложения
- How Queues and Stacks Simplify Problem Solving - Практически сценарии
- Understanding Stacks and Queues - Medium - Real-world примери
Практика
- Cracking Stack and Queue LeetCode Problems - Стъпка по стъпка ръководство