224. Basic Calculator
El texto de la tarea se traduce del ruso para el idioma seleccionado. El código no cambia.
Дана cadena s, представляющая собой допустимое выражение, реализуйте базовый калькулятор для его вычисления и return результат вычисления.
Примечание: нельзя использовать встроенные функции, которые оценивают строки как математические выражения, такие как eval().
Ejemplo:
Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23
C# solución
coincidente/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++ solución
borrador automático, revisar antes de enviar#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 solución
coincidente/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 solución
coincidente/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 solución
coincidente/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 solución
coincidente/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
}Algorithm
Итерация строки выражения в обратном порядке:
Читаем выражение символ за символом, формируя операнды из нескольких цифр, если символ - цифра.
Сохраняем операнды в стек, как только встречаем нецифровой символ.
Обработка выражения внутри скобок:
Когда встречаем открывающую скобку '(', оцениваем выражение, удаляя операнды и операторы из стека до соответствующей закрывающей скобки.
Результат выражения помещаем обратно в стек.
Финальная оценка выражения:
Продолжаем процесс до получения финального результата.
Если стек не пуст после обработки всех символов, оцениваем оставшиеся elementы как одно финальное выражение.
😎
Vacantes para esta tarea
Se muestran vacantes activas con etiquetas coincidentes.
Todavía no hay vacantes activas.