➗ Аритметични изрази: Парсване и Оценка

Парсването и оценката на аритметични изрази е фундаментална задача в компютърните науки. Тази тема е важна за създаване на калкулатори, интерпретатори на езици, компилатори и системи за обработка на формули.

---

📚 Теоретични основи

Аритметичен израз е комбинация от: - Операнди: Числа, променливи, или подизрази - Оператори: +, -, , /, ^, и др. - Скоби*: За променяне на приоритета на операциите

Приоритет на операторите (от висок към нисък):

1. Скоби ( )
2. Унарни оператори (напр. унарен -, !)
3. Степенуване ^
4. Умножение и деление *, /, %
5. Събиране и изваждане +, -

Асоциативност:

• Лява асоциативност: a - b - c = (a - b) - c
• Дясна асоциативност: a ^ b ^ c = a ^ (b ^ c)

---

📝 Парсване чрез рекурсивно спускане (Recursive Descent Parser)

Това е най-гъвкавият и интуитивен метод за обработка на изрази с различни приоритети, скоби и функции. Дефинираме граматика и пишем функция за всяко ниво на приоритет.

Граматика (Примерна):

• Expression: Term + Term | Term - Term | Term
• Term: Factor * Factor | Factor / Factor | Factor
• Factor: ( Expression ) | Number | -Factor | Function(Expression)

Пълна реализация с поддръжка на унарен минус:

#include <iostream>
#include <cctype>
#include <cmath>
using namespace std;

const char* p; // Текуща позиция в низа

// Прототипи на функциите
int expression();
int term();
int factor();

// Парсване на най-базови елементи
int factor() {
    // Пропускаме интервали
    while (*p == ' ') p++;

    // Обработка на скоби
    if (*p == '(') {
        p++; // Пропускаме '('
        int val = expression();
        p++; // Пропускаме ')'
        return val;
    }

    // Обработка на унарен минус
    if (*p == '-') {
        p++;
        return -factor();
    }

    // Обработка на унарен плюс
    if (*p == '+') {
        p++;
        return factor();
    }

    // Четене на цяло число
    int val = 0;
    while (isdigit(*p)) {
        val = val * 10 + (*p - '0');
        p++;
    }
    return val;
}

// Парсване на умножение и деление
int term() {
    int left = factor();
    while (*p == '*' || *p == '/' || *p == '%') {
        char op = *p++;
        int right = factor();
        if (op == '*') left *= right;
        else if (op == '/') left /= right;
        else left %= right;
    }
    return left;
}

// Парсване на събиране и изваждане
int expression() {
    int left = term();
    while (*p == '+' || *p == '-') {
        char op = *p++;
        int right = term();
        if (op == '+') left += right;
        else left -= right;
    }
    return left;
}

int main() {
    string expr = "3 + 5 * (2 - 8)";
    p = expr.c_str();
    cout << "Резултат: " << expression() << endl; // -27

    expr = "10 - 2 * 3";
    p = expr.c_str();
    cout << "Резултат: " << expression() << endl; // 4

    return 0;
}

Разширена версия с поддръжка на степенуване:

int power() {
    int left = factor();
    if (*p == '^') {
        p++;
        int right = power(); // Дясна асоциативност
        return (int)pow(left, right);
    }
    return left;
}

// Променяме term() да извиква power() вместо factor()
int term() {
    int left = power();
    while (*p == '*' || *p == '/') {
        char op = *p++;
        int right = power();
        if (op == '*') left *= right;
        else left /= right;
    }
    return left;
}

---

🔢 Поддръжка на реални числа

За работа с реални числа променяме типа на резултата от int на double:

double factor() {
    while (*p == ' ') p++;

    if (*p == '(') {
        p++;
        double val = expression();
        p++;
        return val;
    }

    if (*p == '-') {
        p++;
        return -factor();
    }

    // Четене на реално число
    double val = 0;
    double decimal = 0;
    int decimals = 0;

    // Цяла част
    while (isdigit(*p)) {
        val = val * 10 + (*p - '0');
        p++;
    }

    // Дробна част
    if (*p == '.') {
        p++;
        while (isdigit(*p)) {
            decimal = decimal * 10 + (*p - '0');
            decimals++;
            p++;
        }
        val += decimal / pow(10, decimals);
    }

    return val;
}

---

⚡ Оценка на логически изрази

Същият подход се прилага за булеви изрази (&&, ||, !).

Приоритет:

• Най-нисък приоритет: || (логическо ИЛИ)
• Среден приоритет: && (логическо И)
• Най-висок приоритет: ! (логическо НЕ) и ()

Реализация с lazy evaluation:

bool logicalFactor();
bool logicalTerm();
bool logicalExpression();

bool logicalFactor() {
    while (*p == ' ') p++;

    if (*p == '!') {
        p++;
        return !logicalFactor();
    }

    if (*p == '(') {
        p++;
        bool val = logicalExpression();
        p++;
        return val;
    }

    // true/false
    if (*p == 't') {
        p += 4; // skip "true"
        return true;
    } else {
        p += 5; // skip "false"
        return false;
    }
}

bool logicalTerm() {
    bool left = logicalFactor();
    while (*p == '&' && *(p+1) == '&') {
        p += 2;
        if (!left) {
            // Lazy evaluation: ако лявата част е false,
            // не оценяваме дясната
            return false;
        }
        bool right = logicalFactor();
        left = left && right;
    }
    return left;
}

bool logicalExpression() {
    bool left = logicalTerm();
    while (*p == '|' && *(p+1) == '|') {
        p += 2;
        if (left) {
            // Lazy evaluation: ако лявата част е true,
            // не оценяваме дясната
            return true;
        }
        bool right = logicalTerm();
        left = left || right;
    }
    return left;
}

Важно: Lazy evaluation е критична оптимизация! Ако лявата страна на && е false, дясната не се оценява. Това е важно когато: - Дясната страна има странични ефекти (напр. извикване на функция) - Дясната страна може да хвърли грешка (напр. деление на нула)

---

🧮 Поддръжка на функции

За калкулатор с вградени функции като sin(), cos(), sqrt(), можем да добавим:

double factor() {
    while (*p == ' ') p++;

    // Проверка за функции
    if (isalpha(*p)) {
        string funcName = "";
        while (isalpha(*p)) {
            funcName += *p++;
        }

        p++; // skip '('
        double arg = expression();
        p++; // skip ')'

        if (funcName == "sin") return sin(arg);
        if (funcName == "cos") return cos(arg);
        if (funcName == "sqrt") return sqrt(arg);
        if (funcName == "abs") return abs(arg);
        if (funcName == "log") return log(arg);

        return 0; // Неизвестна функция
    }

    // ... останалата част от factor()
}

---

🎯 Практически примери

Пример 1: Простичък калкулатор

int main() {
    string expr;
    while (true) {
        cout << "Въведете израз (или 'quit'): ";
        getline(cin, expr);

        if (expr == "quit") break;

        p = expr.c_str();
        try {
            cout << "Резултат: " << expression() << endl;
        } catch (...) {
            cout << "Грешка при парсване!" << endl;
        }
    }
    return 0;
}

Пример 2: Проверка на скоби

bool checkBalanced(const string& expr) {
    int balance = 0;
    for (char c : expr) {
        if (c == '(') balance++;
        if (c == ')') balance--;
        if (balance < 0) return false;
    }
    return balance == 0;
}

---

🔍 Алтернативен метод: Shunting-yard алгоритъм

Shunting-yard алгоритъмът на Дейкстра преобразува инфиксния запис в постфиксен (обратен полски нотация), който е по-лесен за оценка.

Предимства на Recursive Descent: - По-лесен за разбиране и имплементация - Естествено обработва функции и променливи - Лесно се разширява с нови оператори - Добри съобщения за грешки

Предимства на Shunting-yard: - По-компактен код - По-бърз при много операции - Лесно се преобразува в постфиксна форма

---

📋 Задачи за упражнение

1. UVa 727: Equation (Инфикс към Постфикс)
2. SPOJ CALC: Simple Calculator
3. Codeforces 1C: Ancient Berland Circus (изчисляване на формули)
4. Напишете калкулатор с поддръжка на променливи (x = 5, y = x + 3)

---

🏁 Заключение

Recursive Descent е много по-лесен за разширяване от Shunting-yard. Ако задачата изисква поддръжка на функции sin(), max(), или променливи, рекурсивният парсер е правилният избор. Важно е да се разбере връзката между граматиката и структурата на кода - всяко ниво на приоритет има своя функция, която извиква функцията за следващото ниво.