224. Basic Calculator
leetcode hard
#csharp#hard#leetcode#math#stack#string
Task
Дана строка s, представляющая собой допустимое выражение, реализуйте базовый калькулятор для его вычисления и верните результат вычисления.
Примечание: нельзя использовать встроенные функции, которые оценивают строки как математические выражения, такие как eval().
Пример:
Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23
C# solution
matched/originalusing 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);
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int EvaluateExpr(stack<object> stack) {
if (stack.size() == 0 || !(stack.Peek() is int)) {
stack.push(0);
}
int res = (int)stack.pop();
while (stack.size() != 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.size() - 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);
}
}Java solution
matched/originalclass Solution {
public int evaluateExpr(Stack<Object> stack) {
if (stack.empty() || !(stack.peek() instanceof Integer)) {
stack.push(0);
}
int res = (int) stack.pop();
while (!stack.empty() && !((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.charAt(i);
if (Character.isDigit(ch)) {
operand = (int) Math.pow(10, n) * (int) (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);
}
}JavaScript solution
matched/originalclass Solution {
evaluateExpr(stack) {
if (stack.length === 0 || typeof stack[stack.length - 1] !== 'number') {
stack.push(0);
}
let res = stack.pop();
while (stack.length !== 0 && stack[stack.length - 1] !== ')') {
let sign = stack.pop();
if (sign === '+') {
res += stack.pop();
} else {
res -= stack.pop();
}
}
return res;
}
calculate(s) {
let operand = 0;
let n = 0;
let stack = [];
for (let i = s.length - 1; i >= 0; i--) {
let ch = s[i];
if (/\d/.test(ch)) {
operand = Math.pow(10, n) * (parseInt(ch)) + operand;
n += 1;
} else if (ch !== ' ') {
if (n !== 0) {
stack.push(operand);
n = 0;
operand = 0;
}
if (ch === '(') {
let res = this.evaluateExpr(stack);
stack.pop();
stack.push(res);
} else {
stack.push(ch);
}
}
}
if (n !== 0) {
stack.push(operand);
}
return this.evaluateExpr(stack);
}
}Python solution
matched/originalclass Solution:
def evaluate_expr(self, stack):
if not stack or type(stack[-1]) == str:
stack.append(0)
res = stack.pop()
while stack and stack[-1] != ')':
sign = stack.pop()
if sign == '+':
res += stack.pop()
else:
res -= stack.pop()
return res
def calculate(self, s: str) -> int:
stack = []
n, operand = 0, 0
for i in range(len(s) - 1, -1, -1):
ch = s[i]
if ch.isdigit():
operand = (10**n * int(ch)) + operand
n += 1
elif ch != " ":
if n:
stack.append(operand)
n, operand = 0, 0
if ch == '(':
res = self.evaluate_expr(stack)
stack.pop()
stack.append(res)
else:
stack.append(ch)
if n:
stack.append(operand)
return self.evaluate_expr(stack)Go solution
matched/originalpackage 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
}Explanation
Algorithm
Итерация строки выражения в обратном порядке:
Читаем выражение символ за символом, формируя операнды из нескольких цифр, если символ - цифра.
Сохраняем операнды в стек, как только встречаем нецифровой символ.
Обработка выражения внутри скобок:
Когда встречаем открывающую скобку '(', оцениваем выражение, удаляя операнды и операторы из стека до соответствующей закрывающей скобки.
Результат выражения помещаем обратно в стек.
Финальная оценка выражения:
Продолжаем процесс до получения финального результата.
Если стек не пуст после обработки всех символов, оцениваем оставшиеся элементы как одно финальное выражение.
😎