План курса / Все задачи / Алгоритмы и структуры данных

Обратная польская нотация

средне

# решено

Дан массив строк tokens, представляющий выражение в обратной польской нотации. Каждый элемент массива — это либо число, либо один из операторов: +, -, *, /. Нужно вернуть результат вычисления выражения. Гарантируется, что деления на ноль не будет.

Алгоритм вычисления:

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

Например, для выражения ["100", "5", "/", "10", "+"] вычисления будут выглядеть так: (100 / 5) + 10 = 30.

Пример 1:

Ввод: tokens = ["100","5","/","10","+"]
Вывод: 30
Объяснение: после первой операции массив станет [“20”, “10”, “+”], а после второй — [“30”]

Пример 2:

Ввод: tokens = ["10","12","8","-","*"]
Вывод: 40
Объяснение: то же самое, что и (12-8)*10

Пример 3:

Ввод: tokens = ["10"]
Вывод: 10

Ограничения:

len(tokens) >= 1

public class Solution
{
    public static int Calculate(List<string> tokens)
    {
        // Словарь для хранения операций и соответствующих лямбда-функций
        var operations = new Dictionary<string, Func<int, int, int>>
        {
            { "+", (a, b) => a + b },
            { "-", (a, b) => a - b },
            { "/", (a, b) => a / b },
            { "*", (a, b) => a * b }
        };

        // Стек для хранения чисел
        Stack<int> stack = new Stack<int>();

        foreach (string token in tokens)
        {
            if (!operations.ContainsKey(token))
            {
                // token - это число
                stack.Push(int.Parse(token));
                continue;
            }

            // token - это оператор (+, -, *, /)
            int num2 = stack.Pop();
            int num1 = stack.Pop();
            stack.Push(operations[token](num1, num2));
        }

        // Возвращаем результат вычислений
        return stack.Pop();
    }
}

#include <vector>
#include <string>
#include <stack>
#include <unordered_map>
#include <functional>

using namespace std;

int calculate(const vector<string>& tokens) {
    unordered_map<string, function<int(int, int)>> op = {
        {"+", [](int a, int b) { return a + b; }},
        {"-", [](int a, int b) { return a - b; }},
        {"/", [](int a, int b) { return a / b; }},
        {"*", [](int a, int b) { return a * b; }},
    };

    stack<int> stack;

    for (const string& token : tokens) {
        if (op.find(token) == op.end()) {
            // token - это число
            stack.push(stoi(token));
            continue;
        }

        // token - это +, -, * или /
        int num2 = stack.top(); stack.pop();
        int num1 = stack.top(); stack.pop();
        stack.push(op[token](num1, num2));
    }
    return stack.top();
}

package main

import (
    "strconv"
)

func calculate(tokens []string) int {
    op := map[string]func(int, int) int{
        "+": func(a, b int) int { return a + b },
        "-": func(a, b int) int { return a - b },
        "/": func(a, b int) int { return a / b },
        "*": func(a, b int) int { return a * b },
    }

    stack := []int{}

    for _, token := range tokens {
        if _, exists := op[token]; !exists {
            // token - это число
            num, _ := strconv.Atoi(token)
            stack = append(stack, num)
            continue
        }

        // token - это +, -, * или /
        num2 := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        num1 := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        stack = append(stack, op[token](num1, num2))
    }
    return stack[0]
}

import java.util.List;
import java.util.Stack;
import java.util.HashMap;
import java.util.Map;
import java.util.function.BiFunction;

class Solution {
    public int calculate(List<String> tokens) {
        Map<String, BiFunction<Integer, Integer, Integer>> op = new HashMap<>();
        op.put("+", (a, b) -> a + b);
        op.put("-", (a, b) -> a - b);
        op.put("/", (a, b) -> a / b);
        op.put("*", (a, b) -> a * b);

        Stack<Integer> stack = new Stack<>();

        for (String token : tokens) {
            if (!op.containsKey(token)) {
                // token - это число
                stack.push(Integer.parseInt(token));
                continue;
            }

            // token - это +, -, * или /
            int num2 = stack.pop();
            int num1 = stack.pop();
            stack.push(op.get(token).apply(num1, num2));
        }
        return stack.pop();
    }
}

from typing import *

def calculate(tokens: List[str]) -> int:
    op = {
        "+": lambda a, b: a + b,
        "-": lambda a, b: a - b,
        "/": lambda a, b: int(a / b),
        "*": lambda a, b: a * b,
    }
    stack = []

    for token in tokens:
        if token not in op:
            # token - это число
            stack.append(int(token))
            continue
        # token - это +, -, * или /
        num2 = stack.pop()
        num1 = stack.pop()
        stack.append(op[token](num1, num2))
    return stack[0]

export function calculate(tokens) {
    let op = {
        "+": (a, b) => a + b,
        "-": (a, b) => a - b,
        "/": (a, b) => Math.trunc(a / b),
        "*": (a, b) => a * b,
    };
    let stack = [];

    for (let token of tokens) {
        if (!(token in op)) {
            // token - это число
            stack.push(parseInt(token));
            continue;
        }
        // token - это +, -, * или /
        let num2 = stack.pop();
        let num1 = stack.pop();
        stack.push(op[token](num1, num2));
    }
    return stack[0];
}

Оценка сложности

Время: O(n), где n - размер массива tokens
Память: O(n), где n - размер массива tokens