224. Basic Calculator
Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.
Дана chuỗi s, представляющая собой допустимое выражение, реализуйте базовый калькулятор для его вычисления и return результат вычисления.
Примечание: нельзя использовать встроенные функции, которые оценивают строки как математические выражения, такие как eval().
Ví dụ:
Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23
C# lời giải
đã khớp/gốcusing 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++ lời giải
bản nháp tự động, xem lại trước khi gửi#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 lời giải
đã khớp/gốcclass 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 lời giải
đã khớp/gốcclass 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 lời giải
đã khớp/gốcclass 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 lời giải
đã khớp/gốcpackage 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ы как одно финальное выражение.
😎
Vacancies for this task
việc làm đang hoạt động with overlapping task tags are đã hiển thị.
Chưa có việc làm đang hoạt động.