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
