C# | LeetCode

Задача: 772. Basic Calculator III
Сложность: medium

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

Строка выражения содержит только неотрицательные целые числа, операторы '+', '-', '*', '/' и открывающие '(' и закрывающие скобки ')'. Целочисленное деление должно округляться к нулю.

Предполагается, что данное выражение всегда корректно. Все промежуточные результаты будут находиться в диапазоне [-2^31, 2^31 - 1].

Примечание: нельзя использовать встроенные функции для вычисления строк как математических выражений, такие как eval().

Пример:

Input: s = "1+1"
Output: 2

👨‍💻

Алгоритм:

1⃣Определите вспомогательную функцию evaluate, которая принимает оператор и числовые аргументы. Заметьте, что эта функция идентична той, что представлена в подходе "Basic Calculator II". Инициализируйте несколько переменных: стек для хранения промежуточных результатов, curr для отслеживания текущего числа, которое мы строим, и previousOperator для отслеживания предыдущего оператора. Добавьте в строку s случайный символ, который не будет появляться во входных данных, например "@".

2⃣Итерация по входным данным. Для каждого символа c: если c является цифрой, добавьте его к curr. В противном случае, если c == '(', мы начинаем вычисление нового изолированного выражения. В этом случае сохраните previousOperator в стек и установите previousOperator = "+".

3⃣Если c является оператором, то необходимо вычислить значение curr. Используйте функцию evaluate, чтобы применить previousOperator к curr, и добавьте результат в стек. Затем сбросьте curr до нуля и обновите previousOperator = c. Если c == ')', это означает, что мы находимся в конце изолированного выражения и должны полностью его вычислить. Извлекайте из стека до тех пор, пока не достигнете оператора, суммируя все извлеченные числа в curr. Как только достигнете оператора, обновите previousOperator = stack.pop(). Верните сумму всех чисел в стеке.

😎

Решение:

public class Solution {
    private string Evaluate(char operator, string first, string second) {
        int x = int.Parse(first);
        int y = int.Parse(second);
        int res = 0;
        
        if (operator == '+') {
            res = x;
        } else if (operator == '-') {
            res = -x;
        } else if (operator == '*') {
            res = x * y;
        } else {
            res = x / y;
        }
        
        return res.ToString();
    }
    
    public int Calculate(string s) {
        Stack<string> stack = new Stack<string>();
        string curr = "";
        char previousOperator = '+';
        s += "@";
        HashSet<string> operators = new HashSet<string>(new string[] {"+", "-", "*", "/"});
        
        foreach (char c in s) {
            if (char.IsDigit(c)) {
                curr += c;
            } else if (c == '(') {
                stack.Push(previousOperator.ToString());
                previousOperator = '+';
            } else {
                if (previousOperator == '*' || previousOperator == '/') {
                    stack.Push(Evaluate(previousOperator, stack.Pop(), curr));
                } else {
                    stack.Push(Evaluate(previousOperator, curr, "0"));
                }
                
                curr = "";
                previousOperator = c;
                if (c == ')') {
                    int currentTerm = 0;
                    while (!operators.Contains(stack.Peek())) {
                        currentTerm += int.Parse(stack.Pop());
                    }
                    
                    curr = currentTerm.ToString();
                    previousOperator = stack.Pop()[0];
                }
            }
        }
        
        int ans = 0;
        foreach (string num in stack) {
            ans += int.Parse(num);
        }

        return ans;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Please open Telegram to view this post