1、算法的主要思想就是將一個中綴表達式(Infix expression)轉換成便于處理的后綴表達式(Postfix expression)，然后借助于棧這個簡單的數據結構，計算出表達式的結果。
Test No.1: (1.11)=1.110000
Test No.2:1.11+2.22-3.33*4.44/5.55=0.666000
Test No.3:1.11+(2.22-3.33)*4.44/5.55=0.222000
Test No.4:1.11+(2.22-3.33)*(4.44+5.55)/6.66=-0.555000
Test No.5:1.11*((2.22-3.33)*(4.44+5.55))/(6.66+7.77)=-0.852992
Test No.6: (1.11+2.22)*(3.33+4.44)/5.55*6.66=31.048920
Test No.7: (1.11-2.22)/(3.33+4.44)/5.55*(6.66+7.77)/(8.88)=-0.041828
Test No.8: Error: (1.11+2.22)*(3.33+4.44: missing")", please check your expression
Test No.9: Error: (1.11+2.22)*3.33/0+(34-45): divisor cannot be zero
Test No.10: Error:12+89^7: invalid character: ^
classStack(object):
"""
The structure of a Stack.
The user don't have to know the definition.
"""
def__init__(self):
self.__container=list()
def__is_empty(self):
"""
Test if the stack is empty or not
:return: True or False
"""
returnlen(self.__container)==0
defpush(self, element):
"""
Add a new element to the stack
:param element: the element you want to add
:return: None
"""
self.__container.append(element)
deftop(self):
"""
Get the top element of the stack
:return: top element
"""
ifself.__is_empty():
returnNone
returnself.__container[-1]
defpop(self):
"""
Remove the top element of the stack
:return: None or the top element of the stack
"""
returnNoneifself.__is_empty()elseself.__container.pop()
defclear(self):
"""
We'll make an empty stack
:return: self
"""
self.__container.clear()
returnself
在計算器類中，我們將表達式的合法性驗證單獨放在一個函數中完成，但是實際上如果需要，也可以直接放在中綴表達式轉后綴表達式的函數中實現，這樣只需要一次遍歷表達式即可同時完成驗證和轉換工作。但是為了保持結構清晰，還是分開來實現比較好，每個函數盡可能最好一件事情才是比較實在的。
在該計算器類中，有很多種極端的情況沒有被考慮進去，因為那樣的話整個實現的代碼會更多。不過，可以在后期為整個類繼續擴展，添加新的功能也是可以的。目前實現的就是主要框架，包括基本的錯誤檢測和運算，重點時學習運用棧這個看似簡單卻強大的數據結構解決問題。
classCalculator(object):
"""
A simple calculator, just for fun
"""
def__init__(self):
self.__exp=''
def__validate(self):
"""
We have to make sure the expression is legal.
1. We only accept the `()` to specify the priority of a sub-expression. Notes: `[ {` and `] }` will be
replaced by `(` and `)` respectively.
2. Valid characters should be `+`, `-`, `*`, `/`, `(`, `)` and numbers(int, float)
- Invalid expression examples, but we can only handle the 4th case. The implementation will
be much more sophisticated if we want to handle all the possible cases.:
1. `a+b-+c`
2. `a+b+-`
3. `a+(b+c`
4. `a+(+b-)`
5. etc
:return: True or False
"""
ifnotisinstance(self.__exp,str):
print('Error: {}: expression should be a string'.format(self.__exp))
returnFalse
# Save the non-space expression
val_exp=''
s=Stack()
forxinself.__exp:
# We should ignore the space characters
ifx==' ':
continue
ifself.__is_bracket(x)orself.__is_digit(x)orself.__is_operators(x) \
orx=='.':
ifx=='(':
s.push(x)
elifx==')':
s.pop()
val_exp+=x
else:
print('Error: {}: invalid character: {}'.format(self.__exp, x))
returnFalse
ifs.top():
print('Error: {}: missing ")", please check your expression'.format(self.__exp))
returnFalse
self.__exp=val_exp
returnTrue
def__convert2postfix_exp(self):
"""
Convert the infix expression to a postfix expression
:return: the converted expression
"""
# highest priority: ()
# middle: * /
# lowest: + -
converted_exp=''
stk=Stack()
forxinself.__exp:
ifself.__is_digit(x)orx=='.':
converted_exp+=x
elifself.__is_operators(x):
converted_exp+=' '
tp=stk.top()
iftp:
iftp=='(':
stk.push(x)
continue
x_pri=self.__get_priority(x)
tp_pri=self.__get_priority(tp)
ifx_pri > tp_pri:
stk.push(x)
elifx_pri==tp_pri:
converted_exp+=stk.pop()+' '
stk.push(x)
else:
whilestk.top():
ifself.__get_priority(stk.top()) !=x_pri:
converted_exp+=stk.pop()+' '
else:
break
stk.push(x)
else:
stk.push(x)
elifself.__is_bracket(x):
converted_exp+=' '
ifx=='(':
stk.push(x)
else:
whilestk.top()andstk.top() !='(':
converted_exp+=stk.pop()+' '
stk.pop()
# pop all the operators
whilestk.top():
converted_exp+=' '+stk.pop()+' '
returnconverted_exp
def__get_result(self, operand_2, operand_1, operator):
ifoperator=='+':
returnoperand_1+operand_2
elifoperator=='-':
returnoperand_1-operand_2
elifoperator=='*':
returnoperand_1*operand_2
elifoperator=='/':
ifoperand_2 !=0:
returnoperand_1/operand_2
else:
print('Error: {}: divisor cannot be zero'.format(self.__exp))
returnNone
def__calc_postfix_exp(self, exp):
"""
Get the result from a converted postfix expression
e.g. 6 5 2 3 + 8 * + 3 + *
:return: result
"""
assertisinstance(exp,str)
stk=Stack()
exp_split=exp.strip().split()
forxinexp_split:
ifself.__is_operators(x):
# pop two top numbers in the stack
r=self.__get_result(stk.pop(), stk.pop(), x)
ifrisNone:
returnNone
else:
stk.push(r)
else:
# push the converted number to the stack
stk.push(float(x))
returnstk.pop()
def__calc(self):
"""
Try to get the result of the expression
:return: None or result
"""
# Validate
ifself.__validate():
# Convert, then run the algorithm to get the result
returnself.__calc_postfix_exp(self.__convert2postfix_exp())
else:
returnNone
defget_result(self, expression):
"""
Get the result of an expression
Suppose we have got a valid expression
:return: None or result
"""
self.__exp=expression.strip()
returnself.__calc()
"""
Utilities
"""
@staticmethod
def__is_operators(x):
returnxin['+','-','*','/']
@staticmethod
def__is_bracket(x):
returnxin['(',')']
@staticmethod
def__is_digit(x):
returnx.isdigit()
@staticmethod
def__get_priority(op):
ifopin['+','-']:
return0
elifopin['*','/']:
return1
京公網安備 11010802034615號
經營許可證編號：京B2-20210330
