Golang | LeetCode

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

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

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

Пример:

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

👨‍💻

Алгоритм:

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

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

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

😎

Решение:

package main

import (
  "fmt"
  "math"
  "strconv"
  "unicode"
)

type Solution struct{}

func (s Solution) evaluateExpr(stack *[]interface{}) int {
  if len(*stack) == 0 || !isInt((*stack)[len(*stack)-1]) {
    *stack = append(*stack, 0)
  }

  res := pop(stack).(int)

  for len(*stack) != 0 && (*stack)[len(*stack)-1].(rune) != ')' {
    sign := pop(stack).(rune)

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

func (s Solution) calculate(expr string) int {
  operand := 0
  n := 0
  stack := []interface{}{}

  for i := len(expr) - 1; i >= 0; i-- {
    ch := expr[i]

    if unicode.IsDigit(rune(ch)) {
      operand = int(math.Pow(10, float64(n))) * (int(ch-'0')) + operand
      n += 1
    } else if ch != ' ' {
      if n != 0 {
        stack = append(stack, operand)
        n = 0
        operand = 0
      }
      if ch == '(' {
        res := s.evaluateExpr(&stack)
        pop(&stack)
        stack = append(stack, res)
      } else {
        stack = append(stack, rune(ch))
      }
    }
  }

  if n != 0 {
    stack = append(stack, operand)
  }

  return s.evaluateExpr(&stack)
}

func pop(stack *[]interface{}) interface{} {
  if len(*stack) == 0 {
    return nil
  }
  res := (*stack)[len(*stack)-1]
  *stack = (*stack)[:len(*stack)-1]
  return res
}

func isInt(value interface{}) bool {
  _, ok := value.(int)
  return ok
}

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

Please open Telegram to view this post