[LeetCode] Basic Calculator 基本電腦

Implement a basic calculator to evaluate a simple expression string.

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

You may assume that the given expression is always valid.

Some examples:

Note: Do not use the <code>eval</code> built-in library function.

這道題讓我們實作一個基本的電腦來計算簡單的算數表達式，而且題目限制了表達式中隻有加減号，數字，括号和空格，沒有乘除，那麼就沒啥計算的優先級之分了。于是這道題就變的沒有那麼複雜了。我們需要一個棧來輔助計算，用個變量sign來表示目前的符号，我們周遊給定的字元串s，如果遇到了數字，由于可能是個多位數，是以我們要用while循環把之後的數字都讀進來，然後用sign*num來更新結果res；如果遇到了加号，則sign賦為1，如果遇到了符号，則賦為-1；如果遇到了左括号，則把目前結果res和符号sign壓入棧，res重置為0，sign重置為1；如果遇到了右括号，結果res乘以棧頂的符号，棧頂元素出棧，結果res加上棧頂的數字，棧頂元素出棧。代碼如下：

解法一：

下面這種方法和上面的基本一樣，隻不過對于數字的處理略微不同，上面的方法是連續讀入數字，而這種方法是使用了一個變量來儲存讀入的num，是以在遇到其他字元的時候，都要用sign*num來更新結果res，參見代碼如下：

解法二：