abstract：一、算法 1、算法的主要思想就是將一個中綴表達(dá)式(Infix expression)轉(zhuǎn)換成便于處理的后綴表達(dá)式(Postfix expression)，然后借助于棧這個簡單的數(shù)據(jù)結(jié)構(gòu)，計算出表達(dá)式的結(jié)果。 2、關(guān)于如何講普通的表達(dá)式轉(zhuǎn)換成后綴表達(dá)式，以及如何處理后綴表達(dá)式并計算出結(jié)果的具體算法描述不在此
一、算法
1、算法的主要思想就是將一個中綴表達(dá)式(Infix expression)轉(zhuǎn)換成便于處理的后綴表達(dá)式(Postfix expression)，然后借助于棧這個簡單的數(shù)據(jù)結(jié)構(gòu)，計算出表達(dá)式的結(jié)果。
2、關(guān)于如何講普通的表達(dá)式轉(zhuǎn)換成后綴表達(dá)式，以及如何處理后綴表達(dá)式并計算出結(jié)果的具體算法描述不在此敘述了，書上有詳細(xì)的說明。
二、簡易計算器
使用說明
使用該計算器類的簡單示例如下：
# usage
c = Calculator()
print('result: {:f}'.formart(c.get_result('1.11+2.22-3.33*4.44/5.55')))
# output:
result: 0.666000測試案例
為了對這個計算器進(jìn)行有效地檢驗(yàn)，設(shè)計了幾組測試案例，測試結(jié)果如下：
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: ^
實(shí)現(xiàn)代碼
棧的實(shí)現(xiàn)
棧實(shí)際上就是一個被限制操作的表，所有的操作只能在棧的頂端（入棧、出棧等），以下是使用Python代碼實(shí)現(xiàn)的簡單的棧：
class Stack(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 """ return len(self.__container) == 0 def push(self, element): """ Add a new element to the stack :param element: the element you want to add :return: None """ self.__container.append(element) def top(self): """ Get the top element of the stack :return: top element """ if self.__is_empty(): return None return self.__container[-1] def pop(self): """ Remove the top element of the stack :return: None or the top element of the stack """ return None if self.__is_empty() else self.__container.pop() def clear(self): """ We'll make an empty stack :return: self """ self.__container.clear() return self
計算器類的實(shí)現(xiàn)
在計算器類中，我們將表達(dá)式的合法性驗(yàn)證單獨(dú)放在一個函數(shù)中完成，但是實(shí)際上如果需要，也可以直接放在中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式的函數(shù)中實(shí)現(xiàn)，這樣只需要一次遍歷表達(dá)式即可同時完成驗(yàn)證和轉(zhuǎn)換工作。但是為了保持結(jié)構(gòu)清晰，還是分開來實(shí)現(xiàn)比較好，每個函數(shù)盡可能最好一件事情才是比較實(shí)在的。
在該計算器類中，有很多種極端的情況沒有被考慮進(jìn)去，因?yàn)槟菢拥脑捳麄€實(shí)現(xiàn)的代碼會更多。不過，可以在后期為整個類繼續(xù)擴(kuò)展，添加新的功能也是可以的。目前實(shí)現(xiàn)的就是主要框架，包括基本的錯誤檢測和運(yùn)算，重點(diǎn)時學(xué)習(xí)運(yùn)用棧這個看似簡單卻強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)解決問題。
class Calculator(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
"""
if not isinstance(self.__exp, str):
print('Error: {}: expression should be a string'.format(self.__exp))
return False
# Save the non-space expression
val_exp = ''
s = Stack()
for x in self.__exp:
# We should ignore the space characters
if x == ' ':
continue
if self.__is_bracket(x) or self.__is_digit(x) or self.__is_operators(x) \
or x == '.':
if x == '(':
s.push(x)
elif x == ')':
s.pop()
val_exp += x
else:
print('Error: {}: invalid character: {}'.format(self.__exp, x))
return False
if s.top():
print('Error: {}: missing ")", please check your expression'.format(self.__exp))
return False
self.__exp = val_exp
return True
def __convert2postfix_exp(self):
"""
Convert the infix expression to a postfix expression
:return: the converted expression
"""
# highest priority: ()
# middle: * /
# lowest: + -
converted_exp = ''
stk = Stack()
for x in self.__exp:
if self.__is_digit(x) or x == '.':
converted_exp += x
elif self.__is_operators(x):
converted_exp += ' '
tp = stk.top()
if tp:
if tp == '(':
stk.push(x)
continue
x_pri = self.__get_priority(x)
tp_pri = self.__get_priority(tp)
if x_pri > tp_pri:
stk.push(x)
elif x_pri == tp_pri:
converted_exp += stk.pop() + ' '
stk.push(x)
else:
while stk.top():
if self.__get_priority(stk.top()) != x_pri:
converted_exp += stk.pop() + ' '
else:
break
stk.push(x)
else:
stk.push(x)
elif self.__is_bracket(x):
converted_exp += ' '
if x == '(':
stk.push(x)
else:
while stk.top() and stk.top() != '(':
converted_exp += stk.pop() + ' '
stk.pop()
# pop all the operators
while stk.top():
converted_exp += ' ' + stk.pop() + ' '
return converted_exp
def __get_result(self, operand_2, operand_1, operator):
if operator == '+':
return operand_1 + operand_2
elif operator == '-':
return operand_1 - operand_2
elif operator == '*':
return operand_1 * operand_2
elif operator == '/':
if operand_2 != 0:
return operand_1 / operand_2
else:
print('Error: {}: divisor cannot be zero'.format(self.__exp))
return None
def __calc_postfix_exp(self, exp):
"""
Get the result from a converted postfix expression
e.g. 6 5 2 3 + 8 * + 3 + *
:return: result
"""
assert isinstance(exp, str)
stk = Stack()
exp_split = exp.strip().split()
for x in exp_split:
if self.__is_operators(x):
# pop two top numbers in the stack
r = self.__get_result(stk.pop(), stk.pop(), x)
if r is None:
return None
else:
stk.push(r)
else:
# push the converted number to the stack
stk.push(float(x))
return stk.pop()
def __calc(self):
"""
Try to get the result of the expression
:return: None or result
"""
# Validate
if self.__validate():
# Convert, then run the algorithm to get the result
return self.__calc_postfix_exp(self.__convert2postfix_exp())
else:
return None
def get_result(self, expression):
"""
Get the result of an expression
Suppose we have got a valid expression
:return: None or result
"""
self.__exp = expression.strip()
return self.__calc()
"""
Utilities
"""
@staticmethod
def __is_operators(x):
return x in ['+', '-', '*', '/']
@staticmethod
def __is_bracket(x):
return x in ['(', ')']
@staticmethod
def __is_digit(x):
return x.isdigit()
@staticmethod
def __get_priority(op):
if op in ['+', '-']:
return 0
elif op in ['*', '/']:
return 1更多關(guān)于Python實(shí)現(xiàn)簡單的四則運(yùn)算計算器請關(guān)注PHP中文網(wǎng)（ipnx.cn）其他文章！