224. Basic Calculator #

题目 #

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

Example 1:

Input: "1 + 1"
Output: 2

Example 2:

Input: " 2-1 + 2 "
Output: 3

Example 3:

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

Note:

You may assume that the given expression is always valid.
Do not use the eval built-in library function.

题目大意 #

实现一个基本的计算器来计算一个简单的字符串表达式的值。字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格。

解题思路 #

注意点一：算式中有空格，需要跳过
注意点二：算式中会出现负数，负负得正的情况需要特殊处理，所以需要记录每次计算出来的符号

代码 #


package leetcode

import (
	"container/list"
	"fmt"
	"strconv"
)

// 解法一
func calculate(s string) int {
	i, stack, result, sign := 0, list.New(), 0, 1 // 记录加减状态
	for i < len(s) {
		if s[i] == ' ' {
			i++
		} else if s[i] <= '9' && s[i] >= '0' { // 获取一段数字
			base, v := 10, int(s[i]-'0')
			for i+1 < len(s) && s[i+1] <= '9' && s[i+1] >= '0' {
				v = v*base + int(s[i+1]-'0')
				i++
			}
			result += v * sign
			i++
		} else if s[i] == '+' {
			sign = 1
			i++
		} else if s[i] == '-' {
			sign = -1
			i++
		} else if s[i] == '(' { // 把之前计算结果及加减状态压栈，开始新的计算
			stack.PushBack(result)
			stack.PushBack(sign)
			result = 0
			sign = 1
			i++
		} else if s[i] == ')' { // 新的计算结果 * 前一个加减状态 + 之前计算结果
			result = result*stack.Remove(stack.Back()).(int) + stack.Remove(stack.Back()).(int)
			i++
		}
	}
	return result
}

// 解法二
func calculate1(s string) int {
	stack := []byte{}
	for i := 0; i < len(s); i++ {
		if s[i] == ' ' {
			continue
		} else if s[i] == ')' {
			tmp, index := "", len(stack)-1
			for ; index >= 0; index-- {
				if stack[index] == '(' {
					break
				}
			}
			tmp = string(stack[index+1:])
			stack = stack[:index]
			res := strconv.Itoa(calculateStr(tmp))
			for j := 0; j < len(res); j++ {
				stack = append(stack, res[j])
			}
		} else {
			stack = append(stack, s[i])
		}
	}
	fmt.Printf("stack = %v\n", string(stack))
	return calculateStr(string(stack))
}

func calculateStr(str string) int {
	s, nums, tmpStr, res := []byte{}, []int{}, "", 0
	// 处理符号的问题，++得+，--得+，+-、-+得-
	for i := 0; i < len(str); i++ {
		if len(s) > 0 && s[len(s)-1] == '+' && str[i] == '+' {
			continue
		} else if len(s) > 0 && s[len(s)-1] == '+' && str[i] == '-' {
			s[len(s)-1] = '-'
		} else if len(s) > 0 && s[len(s)-1] == '-' && str[i] == '+' {
			continue
		} else if len(s) > 0 && s[len(s)-1] == '-' && str[i] == '-' {
			s[len(s)-1] = '+'
		} else {
			s = append(s, str[i])
		}
	}
	str = string(s)
	s = []byte{}
	for i := 0; i < len(str); i++ {
		if isDigital(str[i]) {
			tmpStr += string(str[i])
		} else {
			num, _ := strconv.Atoi(tmpStr)
			nums = append(nums, num)
			tmpStr = ""
			s = append(s, str[i])
		}
	}
	if tmpStr != "" {
		num, _ := strconv.Atoi(tmpStr)
		nums = append(nums, num)
	}
	res = nums[0]
	for i := 0; i < len(s); i++ {
		if s[i] == '+' {
			res += nums[i+1]
		} else {
			res -= nums[i+1]
		}
	}
	fmt.Printf("s = %v nums = %v res = %v\n", string(s), nums, res)
	return res
}

func isDigital(v byte) bool {
	if v >= '0' && v <= '9' {
		return true
	}
	return false
}

⬅️上一页

下一页➡️