來自*： 吳師兄學(xué)算法

今天的題目來源于 LeetCode 第 22* 號問題： 基本計算器，難度為「 困難 」，根據(jù)評論區(qū)的反饋，在 字節(jié)面試出現(xiàn)過。

一、題目描述

給你一個字符串表達式 s，請你實現(xiàn)一個基本計算器來計算并返回它的值。

示例 1：

輸入：s = "1 + 1"

輸出：2

示例 2：

輸入：s = " 2-1 + 2 "

輸出：*

示例 *：

輸入：s = "(1+(*+*+2)-*)+(*+*)"

輸出：2*

提示：

1 = s.length = * * 10*

s由數(shù)字、'+'、'-'、'('、')'、和 ' '組成

s表示一個有效的表達式

二、題目解析

對于一個表達式來說，它包含三部分：

1、左表達式

2、運算符

*、右表達式

左邊和右邊的表達式可以是一個數(shù)字，也可以是一個括號包起來的表達式；運算符可以是加減。

對于一個只包含加減和括號的表達式來說，是按照從左到右的順序進行計算，但 遇到括號就先算括號里面的。

具體操作如下：

1、使用棧來儲存字符串表達式中的數(shù)字，設(shè)置變量 res 保存計算的結(jié)果，一開始可以認為 res = 0，作為 左表達式，同時當前的運算符為 + ，接下來去變量字符數(shù)組，先去尋找出右表達式出來。

2、獲取字符串里面的每個字符

*、如果當前字符是數(shù)字的話，需要去查看當前字符的后一位是否存在，如果后一位依舊是數(shù)字，那么就需要把后面的數(shù)字累加上來，比如下圖中的 12，查看到 1 時，繼續(xù)查看后面的數(shù)字是 2 ，于是和 1 組成了 12，再向后看發(fā)現(xiàn)是字符，自此，這個數(shù)字 12 就形成了。

*、一旦確定了一個數(shù)字，需要把這個數(shù)字進行一個計算， res = res + sign * value。

*、如果遇到的是運算符 + 或者 - ，那么為了方便計算，所有的操作都視為加法操作，即原先的減法操作就相當于是加一個負數(shù)。

*、如果遇到的是 （ ，根據(jù)數(shù)學(xué)計算規(guī)則，需要先計算括號里面的數(shù)字，而什么時候計算呢？遇到 ) 為止，所以，在遇到 ) 之前需要把之前計算好的結(jié)果存儲起來再計算。

7、如果遇到的是 ），那么就需要把棧中存放的元素取出來了。

三、參考代碼1、Java 代碼// 登錄 AlgoMooc 官網(wǎng)獲取更多算法圖解

021yin.com

// 作者：程序員吳師兄

// 代碼有看不懂的地方一定要私聊咨詢吳師兄呀

021yin.com/problems/basic-calculator

classSolution{

publicintcalculate(String s){

// 使用棧來儲存字符串表達式中的數(shù)字

StackInteger stack = newStackInteger;

// 為了方便計算，所有的操作都視為加法操作

// 那么原先的減法操作就相當于是加一個負數(shù)

// 默認都是正數(shù)

intsign = 1;

// 保存計算的結(jié)果

intres = 0;

// 獲取字符串的長度，然后獲取里面的每個字符

intlength = s.length;

// 獲取字符串里面的每個字符

for( inti = 0; i length; i++) {

// 獲取此時的字符

charch = s.charAt(i);

// 如果當前字符是數(shù)字的話

if(Character.isDigit(ch)) {

// 那么可以通過 - '0' 這個操作把字符轉(zhuǎn)換為整數(shù)

// 相當于轉(zhuǎn)換成了 ascii 碼進行的數(shù)字運算

intvalue = ch - '0';

// 去查看當前字符的后一位是否存在

// 如果操作并且后一位依舊是數(shù)字，那么就需要把后面的數(shù)字累加上來

while(i + 1 length Character.isDigit(s.charAt(i + 1))){

// i 向后移動，直到遇到非數(shù)字為止

i++;

// i 每向后移動一位，當前的值就需要乘以 10

// 比如 s 為 "12*+***"

// 此時 i = 0，那么 value 為 1

// i = 1，那么 value 為 1 * 10 + 2 = 12

// i = 2，那么 value 為 12 * 10 + * = 12*

value = value * 10+ s.charAt(i) - '0';

// 那么把獲取到的數(shù)累加到結(jié)果 res 上

res = res + sign * value;

// 如果是 '+'

} elseif(ch == '+') {

// 那么說明直接加一個正數(shù)

sign = 1;

// 如果是 '-'

} elseif(ch == '-') {

// 那么說明加一個負數(shù)

sign = - 1;

// 如果是 '('

} elseif(ch == '(') {

// 根據(jù)數(shù)學(xué)計算規(guī)則，需要先計算括號里面的數(shù)字

// 而什么時候計算呢？

// 遇到 ) 為止

// 所以，在遇到 ) 之前需要把之前計算好的結(jié)果存儲起來再計算

// ( ) 直接的計算規(guī)則和一開始是一樣的

// 1、先把 ( 之前的結(jié)果存放到棧中

stack.push(res);

// 2、重新初始化 res 為 0

res = 0;

// *、把 ( 左邊的操作符號存放到棧中

// 比如如果是 * - （ 2 + * ） ，那么就是把 -1 存放進去

// 比如如果是 * +（ 2 + * ） ，那么就是把 1 存放進去

stack.push(sign);

// *、為了方便計算，所有的操作都視為加法操作

// 那么原先的減法操作就相當于是加一個負數(shù)

// 默認都是正數(shù)

sign = 1;

// 如果是 ')'

} elseif(ch == ')') {

// 那么就需要把棧中存放的元素取出來了

// 在 ch == '（' 這個判斷語句中，每次都會往棧中存放兩個元素

// 1、先存放左括號外面的結(jié)果

// 2、再存放左括號外面的符號

// 1、先獲取棧頂元素，即左括號外面的符號，查看是 + 還是 -

intformerSign = stack.peek;

// 把棧頂元素彈出

stack.pop;

// 2、再獲取棧頂元素，即左括號結(jié)果

intformerRes = stack.peek;

// 把棧頂元素彈出

stack.pop;

// 那結(jié)果就是括號外面的結(jié)果 + 括號里面的結(jié)果，至于是加正數(shù)還是負數(shù)，取決于左括號外面的符號

res = formerRes + formerSign * res ;

// 返回計算好的結(jié)果

returnres;

2、C++ 代碼// 登錄 AlgoMooc 官網(wǎng)獲取更多算法圖解

021yin.com

// 作者：程序員吳師兄

// 代碼有看不懂的地方一定要私聊咨詢吳師兄呀

021yin.com/problems/basic-calculator

classSolution{

public:

intcalculate( strings) {

// 使用棧來儲存字符串表達式中的數(shù)字

stack int st;

// 為了方便計算，所有的操作都視為加法操作

// 那么原先的減法操作就相當于是加一個負數(shù)

// 默認都是正數(shù)

intsign = 1;

// 保存計算的結(jié)果

intres = 0;

// 獲取字符串的長度，然后獲取里面的每個字符

intlength = s.length;

// 獲取字符串里面的每個字符

for( inti = 0;i length;i++){

// 獲取此時的字符

charch = s[i];

// 如果當前字符是數(shù)字的話

if( ch = '0' ch = '9') {

// 那么可以通過 - '0' 這個操作把字符轉(zhuǎn)換為整數(shù)

// 相當于轉(zhuǎn)換成了 ascii 碼進行的數(shù)字運算

longvalue = ch - '0';

// 去查看當前字符的后一位是否存在

// 如果操作并且后一位依舊是數(shù)字，那么就需要把后面的數(shù)字累加上來

while(i + 1 length s[i+ 1]= '0's[i+ 1]= '9'){

// i 向后移動，直到遇到非數(shù)字為止

i++;

// i 每向后移動一位，當前的值就需要乘以 10

// 比如 s 為 "12*+***"

// 此時 i = 0，那么 value 為 1

// i = 1，那么 value 為 1 * 10 + 2 = 12

// i = 2，那么 value 為 12 * 10 + * = 12*

value = value* 10+ s[i] - '0';

// 那么把獲取到的數(shù)累加到結(jié)果 res 上

res = res + sign * value;

// 如果是 '+'

} elseif(ch == '+'){

// 那么說明直接加一個正數(shù)

sign = 1;

// 如果是 '-'

} elseif(ch == '-'){

// 那么說明加一個負數(shù)

sign = -1;

// 如果是 '('

} elseif(ch == '('){

// 根據(jù)數(shù)學(xué)計算規(guī)則，需要先計算括號里面的數(shù)字

// 而什么時候計算呢？

// 遇到 ) 為止

// 所以，在遇到 ) 之前需要把之前計算好的結(jié)果存儲起來再計算

// ( ) 直接的計算規(guī)則和一開始是一樣的

// 1、先把 ( 之前的結(jié)果存放到棧中

st.push(res);

// 2、重新初始化 res 為 0

res = 0;

// *、把 ( 左邊的操作符號存放到棧中

// 比如如果是 * - （ 2 + * ） ，那么就是把 -1 存放進去

// 比如如果是 * +（ 2 + * ） ，那么就是把 1 存放進去

st.push(sign);

// *、為了方便計算，所有的操作都視為加法操作

// 那么原先的減法操作就相當于是加一個負數(shù)

// 默認都是正數(shù)

sign = 1;

// 如果是 ')'

} elseif(ch == ')'){

// 那么就需要把棧中存放的元素取出來了

// 在 ch == '（' 這個判斷語句中，每次都會往棧中存放兩個元素

// 1、先存放左括號外面的結(jié)果

// 2、再存放左括號外面的符號

// 1、先獲取棧頂元素，即左括號外面的符號，查看是 + 還是 -

intformerSign = st.top;

// 把棧頂元素彈出

st.pop;

// 2、再獲取棧頂元素，即左括號結(jié)果

intformerRes = st.top;

// 把棧頂元素彈出

st.pop;

// 那結(jié)果就是括號外面的結(jié)果 + 括號里面的結(jié)果，至于是加正數(shù)還是負數(shù)，取決于左括號外面的符號

res = formerRes +formerSign*res;

// 返回計算好的結(jié)果

returnres;

*、Python 代碼# 登錄 AlgoMooc 官網(wǎng)獲取更多算法圖解

021yin.com

# 作者：程序員吳師兄

# 代碼有看不懂的地方一定要私聊咨詢吳師兄呀

021yin.com/problems/basic-calculator

classSolution:

defcalculate(self, s: str)- int:

# 使用棧來儲存字符串表達式中的數(shù)字

stack = list

# 為了方便計算，所有的操作都視為加法操作

# 那么原先的減法操作就相當于是加一個負數(shù)

# 默認都是正數(shù)

sign = 1

# 保存計算的結(jié)果

res = 0

# 獲取字符串的長度，然后獲取里面的每個字符

length = len(s)

# 從 0 開始訪問字符串中的每個字符

i = 0

# 獲取字符串里面的每個字符

whilei length:

# 獲取此時的字符

ch = s[i]

ifch == ' ':

i += 1

# 如果當前字符是數(shù)字的話

elifch.isdigit :

# 那么把獲取到的數(shù)累加到結(jié)果 res 上

value = 0

# 去查看當前字符的后一位是否存在

# 如果操作并且后一位依舊是數(shù)字，那么就需要把后面的數(shù)字累加上來

whilei length ands[i].isdigit:

value = value * 10+ ord(s[i]) - ord( '0')

i += 1

# 那么把獲取到的數(shù)累加到結(jié)果 res 上

res += value * sign

# 如果是 '+'

elifch == '+':

# 那么說明直接加一個正數(shù)

sign = 1

i += 1

# 如果是 '-'

elifch == '-':

# 那么說明加一個負數(shù)

sign = -1

i += 1

# 如果是 '('

elifch == '(':

# 根據(jù)數(shù)學(xué)計算規(guī)則，需要先計算括號里面的數(shù)字

# 而什么時候計算呢？

# 遇到 ) 為止

# 所以，在遇到 ) 之前需要把之前計算好的結(jié)果存儲起來再計算

# ( ) 直接的計算規(guī)則和一開始是一樣的

# 1、先把 ( 之前的結(jié)果存放到棧中

stack.append(res)

# 2、重新初始化 res 為 0

res = 0

# *、把 ( 左邊的操作符號存放到棧中

# 比如如果是 * - （ 2 + * ） ，那么就是把 -1 存放進去

# 比如如果是 * +（ 2 + * ） ，那么就是把 1 存放進去

stack.append(sign)

# *、為了方便計算，所有的操作都視為加法操作

# 那么原先的減法操作就相當于是加一個負數(shù)

# 默認都是正數(shù)

sign = 1

i += 1

# 如果是 ')'

elifch == ')':

# 那么就需要把棧中存放的元素取出來了

# 在 ch == '（' 這個判斷語句中，每次都會往棧中存放兩個元素

# 1、先存放左括號外面的結(jié)果

# 2、再存放左括號外面的符號

# 1、先獲取棧頂元素，即左括號外面的符號，查看是 + 還是 -

# 把棧頂元素彈出

formerSign = stack.pop

# 2、再獲取棧頂元素，即左括號結(jié)果

# 把棧頂元素彈出

formerRes = stack.pop

# 那結(jié)果就是括號外面的結(jié)果 + 括號里面的結(jié)果，至于是加正數(shù)還是負數(shù)，取決于左括號外面的符號

res = formerRes + formerSign * res

i += 1

# 返回計算好的結(jié)果

returnres

四、復(fù)雜度分析

時間復(fù)雜度：O(n)，其中 n 為字符串 s 的長度。需要遍歷字符串 s 一次，計算表達式的值。

空間復(fù)雜度：O(n)，其中 n 為字符串 s 的長度?？臻g復(fù)雜度主要取決于棧的空間，棧中的元素數(shù)量不超過 n。

--- EOF ---

推薦↓↓↓