Математические выражения лежат в основе многих компьютерных программ и алгоритмов. Независимо от того, создаете ли вы приложение-калькулятор или реализуете сложный алгоритм, умение вычислять математические выражения является важнейшим навыком. В этой статье блога мы рассмотрим различные методы вычисления математических выражений с использованием стеков — фундаментальной структуры данных в информатике. Итак, хватайте свой любимый напиток и давайте окунемся в мир вычисления выражений на основе стека!

Метод 1: оценка постфиксных выражений.
Один популярный подход к оценке математических выражений заключается в преобразовании их в постфиксную нотацию (также известную как обратная польская нотация) и последующем использовании стека для выполнения оценки. Давайте рассмотрим пример, чтобы проиллюстрировать этот метод:

Выражение: 3 + 4 * 2 – 1

Шаг 1. Преобразуйте выражение в постфиксную запись:
3 4 2 * + 1 –

Шаг 2. Оцените постфиксное выражение с помощью стека:

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

Пример кода (Python):

def evaluate_postfix(expression):
    stack = []
    operators = {'+': lambda a, b: a + b, '-': lambda a, b: a - b, '*': lambda a, b: a * b, '/': lambda a, b: a / b}
    for token in expression:
        if token.isdigit():
            stack.append(int(token))
        else:
            operand2 = stack.pop()
            operand1 = stack.pop()
            result = operators[token](operand1, operand2)
            stack.append(result)
    return stack.pop()
expression = "3 4 2 * + 1 -"
result = evaluate_postfix(expression)
print(result)  # Output: 9

Метод 2: оценка инфиксного выражения.
Хотя постфиксная оценка эффективна и проста, инфиксная нотация является наиболее распространенным способом выражения математических выражений. Чтобы оценить инфиксные выражения с помощью стека, нам необходимо преобразовать их в постфиксную нотацию, а затем применить описанный выше метод постфиксной оценки.

Пример кода (Python):

def infix_to_postfix(expression):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
    stack = []
    postfix = []
    for token in expression:
        if token.isdigit():
            postfix.append(token)
        elif token == '(':
            stack.append(token)
        elif token == ')':
            while stack and stack[-1] != '(':
                postfix.append(stack.pop())
            stack.pop()  # Discard the '('
        else:
            while stack and stack[-1] != '(' and precedence[token] <= precedence.get(stack[-1], 0):
                postfix.append(stack.pop())
            stack.append(token)
    while stack:
        postfix.append(stack.pop())
    return " ".join(postfix)
def evaluate_infix(expression):
    postfix_expression = infix_to_postfix(expression)
    result = evaluate_postfix(postfix_expression)
    return result
expression = "3 + 4 * 2 - 1"
result = evaluate_infix(expression)
print(result)  # Output: 9

Метод 3. Оценка с использованием деревьев выражений.
Другой подход к оценке математических выражений заключается в создании дерева выражений. Дерево выражений представляет структуру выражения в иерархическом порядке. Затем мы можем обойти дерево и выполнить оценку.

Пример кода (Python):

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
def build_expression_tree(expression):
    stack = []
    for token in expression:
        if token.isdigit():
            node = Node(token)
            stack.append(node)
        else:
            node = Node(token)
            node.right = stack.pop()
            node.left = stack.pop()
            stack.append(node)
    return stack.pop()
def evaluate_expression_tree(root):
    if root.value.isdigit():
        return int(root.value)
    else:
        left_result = evaluate_expression_tree(root.left)
        right_result = evaluate_expression_tree(root.right)
        return evaluate_operation(left_result, right_result, root.value)
def evaluate_operation(a, b, operator):
    if operator == '+':
        return a + b
    elif operator == '-':
        return a - b
    elif operator == '*':
        return a * b
    elif operator == '/':
        return a / b
expression = ["3", "+", "4", "*", "2", "-", "1"]
root = build_expression_tree(expression)
result = evaluate_expression_tree(root)
print(result)  # Output: 9

В этой статье блога мы рассмотрели три различных метода вычисления математических выражений с использованием стеков. Мы обсудили метод постфиксной оценки, преобразование инфиксных выражений в постфикснотацию и оценку выражений с использованием деревьев выражений. У каждого метода есть свои преимущества и варианты использования, поэтому важно выбрать тот, который лучше всего соответствует вашим конкретным требованиям.

Поняв эти методы, у вас теперь есть инструменты для решения математических задач по вычислению выражений в ваших усилиях по программированию. Так что давай, попробуй и раскрой мощь стеков в подсчете этих чисел!