LeetCode 27. Basic Calculator II.jpg
LeetCode 27. Basic Calculator II
Description
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
Example 1:
Input: "3+2*2"
Output: 7
Example 2:
Input: " 3/2 "
Output: 1
Example 3:
Input: " 3+5 / 2 "
Output: 5
Note:
You may assume that the given expression is always valid.
Do not use the eval built-in library function.
描述
實現(xiàn)一個基本的計算器來計算一個簡單的字符串表達式的值舀凛。
字符串表達式僅包含非負整數(shù)召衔，+， - 捷犹，*恳谎，/ 四種運算符和空格 肥荔。 整數(shù)除法僅保留整數(shù)部分骇两。
示例 1:
輸入: "3+2*2"
輸出: 7
示例 2:
輸入: " 3/2 "
輸出: 1
示例 3:
輸入: " 3+5 / 2 "
輸出: 5
說明：
你可以假設所給定的表達式都是有效的。
請不要使用內(nèi)置的庫函數(shù) eval拳喻。
思路
- 我們使用兩個棧來實現(xiàn)表達式求值.
- 其中一個用來存儲數(shù)字哭当，另一個來存儲符號.
- 我們從給定的字符串中不斷的取出數(shù)字和符號，若是數(shù)字冗澈，我們將其壓入數(shù)字棧钦勘，如果是符號，我們和當前棧頂?shù)姆栠M行比較渗柿，如果當前符號的優(yōu)先級小于等于棧頂元素的符號个盆，我們彈出符號棧頂元素，并用此符號對數(shù)字棧棧頂?shù)膬蓚€元素進行運算朵栖，并將運算的結果重新壓入數(shù)字棧颊亮，直到當前符號大于符號棧棧頂元素或者符號棧為空.
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2019-01-28 20:41:10
# @Last Modified by: 何睿
# @Last Modified time: 2019-01-28 21:28:48
class Solution:
def calculate(self, s):
"""
:type s: str
:rtype: int
"""
# 聲明兩個棧，用于存儲數(shù)字和操作符
stack1, stack2 = [], []
# num用于從字符串中取出數(shù)字
num = 0
for item in s:
# 取數(shù)字
if item.isdigit():
num = num * 10 + ord(item) - ord("0")
# 如果為空則繼續(xù)執(zhí)行
elif item == " ":
continue
else:
# 向數(shù)字棧中添加數(shù)字
stack1.append(num)
# 數(shù)字重置為0
num = 0
# 如果符號棧為空陨溅，將當前符號壓入棧
if not stack2:
stack2.append(item)
else:
# 如果當前操作符優(yōu)先級小于等于符號棧棧頂操作符终惑，我們持續(xù)進行運算
while stack2 and self.compare(stack2[-1], item):
# 從數(shù)字棧中取出兩個數(shù)字
num1, num2 = stack1.pop(), stack1.pop()
# 對這兩個數(shù)字進行當前符號的運算，并將運算結果壓入數(shù)字棧
stack1.append(self.operate(stack2.pop(), num2, num1))
# 將當前符號壓入符號棧
stack2.append(item)
# 將最后剩下的數(shù)字壓入數(shù)子棧
stack1.append(num)
# 對剩下的數(shù)字和符號進行運算
while stack2 and stack1:
num1, num2 = stack1.pop(), stack1.pop()
stack1.append(self.operate(stack2.pop(), num2, num1))
return stack1.pop()
def operate(self, operator, num1, num2):
# 運算函數(shù)
if operator == "+": return num1 + num2
if operator == "-": return num1 - num2
if operator == "*": return num1 * num2
if operator == "/": return num1 // num2
def compare(self, op1, op2):
# op2的優(yōu)先級>=op1的優(yōu)先級返回True
# 否則返回False
if (op1 == "+" or op1 == "-") and (op2 == '+' or op2 == "-"):
return True
if (op1 == "*" or op1 == "/") and (op2 == '*' or op2 == '/'):
return True
if (op1 == "*" or op1 == "/") and (op2 == '+' or op2 == "-"):
return True
return False
