abstract：一、算法 1、算法的主要思想就是将一个中缀表达式(Infix expression)转换成便于处理的后缀表达式(Postfix expression)，然后借助于栈这个简单的数据结构，计算出表达式的结果。 2、关于如何讲普通的表达式转换成后缀表达式，以及如何处理后缀表达式并计算出结果的具体算法描述不在此
一、算法
1、算法的主要思想就是将一个中缀表达式(Infix expression)转换成便于处理的后缀表达式(Postfix expression)，然后借助于栈这个简单的数据结构，计算出表达式的结果。
2、关于如何讲普通的表达式转换成后缀表达式，以及如何处理后缀表达式并计算出结果的具体算法描述不在此叙述了，书上有详细的说明。
二、简易计算器
使用说明
使用该计算器类的简单示例如下：
# usage c = Calculator() print('result: {:f}'.formart(c.get_result('1.11+2.22-3.33*4.44/5.55'))) # output: result: 0.666000
测试案例
为了对这个计算器进行有效地检验，设计了几组测试案例，测试结果如下：
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: ^
实现代码
栈的实现
栈实际上就是一个被限制操作的表，所有的操作只能在栈的顶端（入栈、出栈等），以下是使用Python代码实现的简单的栈：
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
计算器类的实现
在计算器类中，我们将表达式的合法性验证单独放在一个函数中完成，但是实际上如果需要，也可以直接放在中缀表达式转后缀表达式的函数中实现，这样只需要一次遍历表达式即可同时完成验证和转换工作。但是为了保持结构清晰，还是分开来实现比较好，每个函数尽可能最好一件事情才是比较实在的。
在该计算器类中，有很多种极端的情况没有被考虑进去，因为那样的话整个实现的代码会更多。不过，可以在后期为整个类继续扩展，添加新的功能也是可以的。目前实现的就是主要框架，包括基本的错误检测和运算，重点时学习运用栈这个看似简单却强大的数据结构解决问题。
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
更多关于Python实现简单的四则运算计算器请关注PHP中文网（m.sbmmt.com）其他文章！
