由于是一道會(huì)員專享的加練題，所以題解很少，并且大都是在227基本計(jì)算器II的基礎(chǔ)上，對(duì)括號(hào)內(nèi)的運(yùn)算直接做了遞歸處理，此外還有一些更慢的算法。這里分享一個(gè)非遞歸的思路，基于世界上最簡(jiǎn)單的語(yǔ)言Python實(shí)現(xiàn)。

題目描述：

實(shí)現(xiàn)一個(gè)基本的計(jì)算器來(lái)計(jì)算簡(jiǎn)單的表達(dá)式字符串。
表達(dá)式字符串可以包含左括號(hào) (和右括號(hào))，加號(hào) + 和減號(hào) -，非負(fù) 整數(shù)和空格 。
表達(dá)式字符串只包含非負(fù)整數(shù)， +, -, *, / 操作符，左括號(hào) ( ，右括號(hào) )和空格。整數(shù)除法需要向下截?cái)唷?br> 你可以假定給定的字符串總是有效的。所有的中間結(jié)果的范圍為 [-2147483648, 2147483647]。
一些例子：
"1 + 1" = 2
" 6-4 / 2 " = 4
"2*(5+5*2)/3+(6/2+8)" = 21
"(2+6* 3+5- (3*14/7+2)*5)+3"=-12
注：不要 使用內(nèi)置庫(kù)函數(shù) eval。
來(lái)源：力扣（LeetCode）鏈接：https://leetcode-cn.com/problems/basic-calculator-iii著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

在【基本計(jì)算器II】的基礎(chǔ)上，我們可以用遞歸的方法將括號(hào)中的運(yùn)算作為參數(shù)傳入，直接做遞歸運(yùn)算，這是最為方便快捷的做法。此外，我們也可以不使用遞歸，防止括號(hào)過(guò)多的情況下函數(shù)棧溢出。

相比于【基本計(jì)算器II】，我們需要額外考慮的只有括號(hào)的處理，其他操作都基本相同。在解題之前，我們可以分析出一個(gè)規(guī)律：'('前面一定不是數(shù)字，而其他符號(hào)前面一定是數(shù)字。

因此，遇到'('符號(hào)，我們可以把它前面的符號(hào)壓入棧中做個(gè)標(biāo)記，在處理完括號(hào)里的運(yùn)算后，再回頭做對(duì)應(yīng)的運(yùn)算。遇到')'符號(hào)時(shí)，我們需要先將棧頂?shù)乃袛?shù)字累加，直到棧頂變成運(yùn)算符字符串為止。此時(shí)意味著我們已經(jīng)把這對(duì)括號(hào)內(nèi)的運(yùn)算都處理完了，得到了括號(hào)內(nèi)的運(yùn)算結(jié)果。將棧頂?shù)倪\(yùn)算符取出后，我們對(duì)括號(hào)的結(jié)果進(jìn)行對(duì)應(yīng)的運(yùn)算就可以了。

Python實(shí)現(xiàn)的代碼如下：

from collections import deque

class Solution:

    # Deal with the operations

    def solve(self, operand: int, sign: str, stack: deque) -> int:

        if sign == '+':
            return operand
        elif sign == '-':
            return -operand
        elif sign == '*':
            return stack.pop() * operand
        elif sign == '/':
            return int(stack.pop() / operand)

    def calculate(self, s: str) -> int:
        stack = deque()
        operand = 0
        sign = '+'

        for c in s:
            if c == ' ':
                # Ignore the space
                continue
            elif c.isdigit():
                operand = operand * 10 + int(c)
            elif c == '(':
                # An integer cannot be just before a '(', so only save the previous operator here
                stack.append(sign)
                sign = '+'
            else:
                # Do the default calculation
                result = self.solve(operand, sign, stack)

                operand = 0

                if c == ')':
                    # Summate all the intergers on the top of a stack until meet an operator, which means
                    # we need to do the corresponding operation with the summation value as an operand
                    while isinstance(stack[-1], int):
                        result += stack.pop()

                    sign = stack.pop()

                    operand = self.solve(result, sign, stack)
                    sign = '+'

                else:
                    # Push the result value to the stack for later summation
                    # Save the operator for calculation in a coming loop

                    sign = c

                    stack.append(result)

        # The calculation doesn't finish here. We always do actual calculation in later loops, so
        # at present we should deal with the operand gotten in the last loop.
        last = self.solve(operand, sign, stack)
        stack.append(last)

        # + and - have the lowest priority
        return sum(stack)

在這樣的解法中，運(yùn)算時(shí)間約和字符串長(zhǎng)度 N 成正比，復(fù)雜度為 O(N)；需要的棧長(zhǎng)度不超過(guò)字符串中運(yùn)算符的數(shù)量，小于 N/2，復(fù)雜度為 O(N)。