題目描述
實(shí)現(xiàn)一個(gè)基本的計(jì)算器來(lái)計(jì)算一個(gè)簡(jiǎn)單的字符串表達(dá)式的值父腕。
字符串表達(dá)式可以包含左括號(hào) ( ，右括號(hào) )柠逞，加號(hào) + 倦蚪，減號(hào) -，非負(fù)整數(shù)和空格 边苹。
示例
示例 1：
輸入: "1 + 1"
輸出: 2
示例2：
輸入: " 2-1 + 2 "
輸出: 3
示例3：
輸入: "(1+(4+5+2)-3)+(6+8)"
輸出: 23
說(shuō)明：
- 你可以假設(shè)所給定的表達(dá)式都是有效的。
- 請(qǐng)不要使用內(nèi)置的庫(kù)函數(shù) eval裁僧。
解答方法
方法一：棧和不反轉(zhuǎn)字符串
思路
- 把字符串中所有的數(shù)字和數(shù)字前面的符號(hào)看做一個(gè)整體个束，以正負(fù)數(shù)的形式表達(dá)，這樣在計(jì)算時(shí)全看做加法聊疲。
- 遇到括號(hào)時(shí)先保存之前的計(jì)算結(jié)果茬底，計(jì)算完括號(hào)里的之后在于之前的結(jié)果相加。
- 結(jié)果的保存用棧來(lái)實(shí)現(xiàn)
代碼
class Solution:
def calculate(self, s: str) -> int:
stack = []
res = 0
nums = 0
sign = 1
for ch in s:
if ch.isdigit():
nums = nums*10 + int(ch)
if ch is '+':
res += sign * nums
sign = 1
nums = 0
if ch is '-':
res += sign * nums
sign = -1
nums = 0
if ch is '(':
stack.append(res)
stack.append(sign)
sign = 1
res = 0
if ch is ')':
res += sign * nums
res *= stack.pop()
res += stack.pop()
nums = 0
return res + sign*nums
時(shí)間復(fù)雜度
O(N)获洲，其中 N 指的是字符串的長(zhǎng)度阱表。
空間復(fù)雜度
O(N)，其中 N 指的是字符串的長(zhǎng)度贡珊。
