Структуры данных — Разбор выражений

Разбор выражений — наиболее классический сценарий применения структуры данных стек.

Разбор выражений демонстрирует, как использовать стеки для преобразования инфиксных, префиксных и постфиксных выражений, а также для вычисления выражений.

Три формы записи выражений

Преобразование инфиксного выражения A + B * C в постфиксное — пошаговая демонстрация
Шаг 1Читаем AОперанд, выводим напрямуюВывод: AСтек: пуст
Шаг 2Читаем +Оператор, помещаем в стекВывод: AСтек: +
Шаг 3Читаем BОперанд, выводим напрямуюВывод: ABСтек: +
Шаг 4Читаем ** имеет более высокий приоритет, чем +, помещаем в стекВывод: ABСтек: +*
Шаг 5Читаем CОперанд, выводим напрямуюВывод: ABCСтек: +*
Шаг 6КонецИзвлекаем все операторы из стекаВывод: ABC*+Стек: пуст
Итоговый результат: A + B * C → A B C * +

При обработке математических выражений в компьютере существуют три способа представления:

TypeПозиция оператораПримерСложность вычисленияНеобходимость скобок
Инфиксное выражениеМежду операндами (человеческое соглашение)A + B * CНеобходимо учитывать приоритет и скобкиНеобходимы
Префиксное выражение(польская нотация)Перед операндами+ A * B CДостаточно одного проходаНе требуется
Постфиксное выражение(обратная польская запись)После операндовA B C * +Достаточно одного проходаНе требуется

Самое большое преимущество постфиксных и префиксных выражений заключается в том, что при вычислении не нужно учитывать приоритет операторов или скобки; достаточно последовательно просматривать слева направо.

Алгоритм преобразования инфиксной записи в постфиксную (идея алгоритма сортировочной станции)

Основной алгоритм преобразования инфиксного выражения в постфиксное реализуется с помощью стека. Основной процесс следующий:

  1. Сканировать инфиксное выражение слева направо
  2. При обнаруженииоперанда(цифра/буква) выводите его напрямую
  3. При обнаруженииоператора, сравните его приоритет с оператором на вершине стека:
    • Если оператор на вершине стека имеет более высокий или равный приоритет, извлеките верхний элемент и выведите его
    • Повторяйте этот процесс, пока текущий оператор не сможет быть помещён в стек
  4. При обнаружениилевой круглой скобки, поместите её прямо в стек
  5. При встречеправой скобки, продолжайте извлекать операторы с вершины стека и выводить их, пока не встретится левая скобка (левая скобка извлекается, но не выводится)
  6. После завершения сканирования извлекайте и выводите оставшиеся в стеке операторы по одному

Пример

#include <stdio.h>
#include <ctype.h> /* функция isalnum */
#include <string.h>

#define MAX 100

char stack[MAX];
int top = -1;

void push(char c) { stack[++top] = c; }
char pop() { return (top == -1) ? -1 : stack[top--]; }

/* Возвращает приоритет оператора: чем больше число, тем выше приоритет */
int precedence(char op) {
    if (op == '+' || op == '-') return 1;  /* Сложение и вычитание имеют самый низкий приоритет */
    if (op == '*' || op == '/') return 2;  /* Умножение и деление имеют более высокий приоритет */
    if (op == '^') return 3;               /* Возведение в степень имеет наивысший приоритет */
    return 0;  /* Не является оператором */
}

Инфиксное выражение в постфиксное выражение
Параметры: infix - входная строка инфиксного выражения
postfix - выходной буфер постфиксного выражения */
void infixToPostfix(char* infix, char* postfix) {
    int i = 0, j = 0;
    char c;

    while ((c = infix[i++]) != '\0') {
        /* Операнд (буква или цифра): выводить напрямую */
        if (isalnum(c)) {
            postfix[j++] = c;
        }
        /* Левая скобка: поместить в стек напрямую */
        else if (c == '(') {
            push(c);
        }
        /* Правая скобка: выполнять pop, пока не встретится левая скобка */
        else if (c == ')') {
            while (top != -1 && stack[top] != '(') {
                postfix[j++] = pop();
            }
            pop();  /* Выполнить pop для левой скобки '(' но не выводить */
        }
        /* Оператор: обработать приоритет */
        else {
            while (top != -1 &&
                   precedence(stack[top]) >= precedence(c) &&
                   stack[top] != '(') {
                postfix[j++] = pop();
            }
            push(c);
        }
    }

    /* Выполнить pop всех оставшихся операторов из стека */
    while (top != -1) {
        postfix[j++] = pop();
    }
    postfix[j] = '\0';  /* Конец строки */
}

int main() {
    char infix[] = "A+B*C";
    char postfix[MAX];

    infixToPostfix(infix, postfix);
    printf("Инфикс: %s\n", infix);      /* Вывод: Инфикс: A+B*C */
    printf("Постфикс: %s\n", postfix);    /* Вывод: Постфикс: ABC*+ */
    return 0;
}

Вычисление постфиксного выражения

Вычисление постфиксного выражения 5 3 + 2 * — пошаговая демонстрация
Шаг 1Читаем 5Число, помещаем в стекСтек: 5
Шаг 2Читаем 3Число, помещаем в стекСтек: 5 3
Шаг 3Читаем +Извлекаем 3 и 5, вычисляем 5+3=8, помещаем результат в стекСтек: 85+3=8
Шаг 4Читаем 2Число, помещаем в стекСтек: 8 2
Шаг 5Читаем *Извлекаем 2 и 8, вычисляем 8*2=16, помещаем результат в стекСтек: 168*2=16
РезультатКонецНа стеке остаётся только 16, что и является вычисленным результатомРезультат = 16
Постфиксная запись 53+2* = 16 (эквивалентно инфиксной записи (5+3)*2)

При использовании постфиксного выражения вычисление с помощью стека очень просто: помещайте операнды в стек; при встрече оператора извлеките два операнда, вычислите и поместите результат обратно.

Пример

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>

#define MAX 100

int stack[MAX];
int top = -1;

void push(int val) { stack[++top] = val; }
int pop() { return stack[top--]; }

/* Вычислить значение постфиксного выражения
Параметры: postfix — постфиксное выражение (операнды — однозначные цифры 0-9)
Возвращаемое значение: вычисленный результат выражения */
int evaluatePostfix(char* postfix) {
    int i = 0;
    char c;

    while ((c = postfix[i++]) != '\0') {
        /* Операнд: преобразовать в число и поместить в стек */
        if (isdigit(c)) {
            push(c - '0');  /* '3' преобразовано в целое число 3 */
        }
        /* Оператор: извлечь два операнда, вычислить и поместить обратно */
        else {
            int b = pop();  /* Второй операнд (правый операнд) */
            int a = pop();  /* Первый операнд (левый операнд) */
            switch (c) {
                case '+': push(a + b); break;
                case '-': push(a - b); break;
                case '*': push(a * b); break;
                case '/': push(a / b); break;
            }
        }
    }
    return pop();  /* Последний элемент в стеке — окончательный результат */
}

int main() {
    /* Постфиксное выражение "23+5*" эквивалентно инфиксному выражению "(2+3)*5" = 25 */
    char postfix[] = "23+5*";
    int result = evaluatePostfix(postfix);
    printf("Postfix %s = %d\n", postfix, result);  /* Вывод: Postfix 23+5* = 25 */
    return 0;
}

При вычислении постфиксного выражения порядок извлечения операндов критически важен: первым извлекаетсяправый операнд(b), а позже —левый операнд(a). Это особенно важно для некоммутативных операций, таких как вычитание и деление; изменение порядка приведёт к неверным результатам.

Полный пример: вычисление инфиксного выражения

Связывание двух вышеописанных шагов вместе даёт полноценный калькулятор: инфикс → постфикс → вычисление.

Пример

#include <stdio.h>
#include <ctype.h>

#define MAX 100

/* Вспомогательная функция приоритета операторов (как выше), функция вычисления (как выше), функция преобразования (как выше) */
/* Для краткости определённые выше функции здесь опущены; включите их при фактическом использовании */

int main() {
    char infix[] = "5+3*2";            /* Инфиксное выражение */
    char postfix[MAX];
    infixToPostfix(infix, postfix);    /* Шаг 1: Преобразование в постфиксную запись */

    printf("Infix: %s\n", infix);       /* Вывод: Infix: 5+3*2 */
    printf("Postfix: %s\n", postfix);     /* Вывод: Postfix: 532*+ */

    int result = evaluatePostfix(postfix);  /* Шаг 2: Вычислить */
    printf("Result: %s = %d\n", infix, result);
    /* Вывод: Result: 5+3*2 = 11 */
    return 0;
}
Другие расширения