Задача: 224. Basic Calculator
Сложность: hard

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

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

Пример:

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

👨‍💻 Алгоритм:

1⃣Итерация строки выражения в обратном порядке:
Читаем выражение символ за символом, формируя операнды из нескольких цифр, если символ - цифра.
Сохраняем операнды в стек, как только встречаем нецифровой символ.

2⃣Обработка выражения внутри скобок:
Когда встречаем открывающую скобку '(', оцениваем выражение, удаляя операнды и операторы из стека до соответствующей закрывающей скобки.
Результат выражения помещаем обратно в стек.

3⃣Финальная оценка выражения:
Продолжаем процесс до получения финального результата.
Если стек не пуст после обработки всех символов, оцениваем оставшиеся элементы как одно финальное выражение.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {

    public int EvaluateExpr(Stack<object> stack) {
        if (stack.Count == 0 || !(stack.Peek() is int)) {
            stack.Push(0);
        }

        int res = (int)stack.Pop();

        while (stack.Count != 0 && !((char)stack.Peek() == ')')) {
            char sign = (char)stack.Pop();

            if (sign == '+') {
                res += (int)stack.Pop();
            } else {
                res -= (int)stack.Pop();
            }
        }
        return res;
    }

    public int Calculate(string s) {
        int operand = 0;
        int n = 0;
        Stack<object> stack = new Stack<object>();

        for (int i = s.Length - 1; i >= 0; i--) {
            char ch = s[i];

            if (char.IsDigit(ch)) {
                operand = (int)Math.Pow(10, n) * (ch - '0') + operand;
                n += 1;
            } else if (ch != ' ') {
                if (n != 0) {
                    stack.Push(operand);
                    n = 0;
                    operand = 0;
                }
                if (ch == '(') {
                    int res = EvaluateExpr(stack);
                    stack.Pop();
                    stack.Push(res);
                } else {
                    stack.Push(ch);
                }
            }
        }

        if (n != 0) {
            stack.Push(operand);
        }

        return EvaluateExpr(stack);
    }
}

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