201712 TDD Coding Practice Arithmetic (Double Stack Algorithm) in Python - xiaoxianfaye/Courses GitHub Wiki

1 Problem

编写一个简单的计算器，该计算器目前只需要支持单位正整数的加、减、乘、除运算，并支持用括号表示优先级别。和我们小学时学过的算术规则一致，乘法和除法的优先级一样，加法和减法的优先级一样。乘除法的优先级高于加减法。括号的优先级最高。同一优先级的运算顺序为自左向右。几个简单的例子如下：

1+2 = 3
3-(2+1) = 0
4-(3-1) = 2
1+2*3 = 7
4/2*2 = 4
(1+2)*2+3 = 9

要求提供一个名为eval的API，输入字符串类型的表达式，输出整数类型的运算结果。

2 Showcase & Discuss

请学员展示自己之前的设计思路和实现方式，大家可以互相点评、讨论。以学员为主，讲师为辅。

3 Analysis

分析：定义清楚问题是什么。

3.1 Problem Domain

3.1.1 Concepts

  • 表达式：Expression
  • 操作数：Operand
  • 操作符：Operator
  • 子表达式：SubExpression

3.1.2 Boundaries

  • 进入系统的表达式是规格化后合法的表达式。
  • 表达式的规格化和合法性校验放在系统边界以外。
  • 操作数均为单位正整数。
  • 操作符只包括：+ - * /，其中除法均为整除。
  • 子表达式用圆括号()括起来，可嵌套。
  6 * (( 1+ 3) / 2) --规格化--> 6*((1+3)/2)

  Illegal Expressions (可以让学员讲一下怎么不合法)：
  (-16)**2     多位正整数、非法操作符
  2++3         非法操作符
  (1+2)-3)     括号不对称

3.1.3 Rules

  • 操作符优先级：+ 和 - 同级， * 和 / 同级， * 和 / 优先级高于 + 和 -。
  • 优先级相同的情况下，“+ - * /”操作符都是左结合 (自左向右进行运算)。
  • 先看优先级、再看结合性。
  • ()优先级最高。

3.2 Double-stack Algorithm

用以下几个表达式讲解双栈算法，可以让学员来讲。

1+2
3+2-1
1+2*3
1+2*3-1
  • 当前字符为操作数时，直接压栈；
  • 当前字符为操作符时，如果操作符栈为空或当前操作符的优先级高于栈顶操作符时，压栈；如果当前操作符的优先级低于或等于栈顶操作符时，从操作数栈弹出两个操作数(注意顺序)，从操作符栈弹出一个操作符，进行运算，并将运算结果压入操作数栈；
  • 当到达表达式末尾时，依次弹出两个操作数和一个操作符进行运算，并将运算结果压入操作数栈，如此反复，直到操作符栈为空，此时操作数栈应该只有一个最终的运算结果。

Quiz (向学员提问，看看是否真的理解了双栈算法)
Q：操作数栈和操作符栈的大小是否有最大值？如果有，分别是多少？
A：操作数栈的最大长度是3，操作符栈的最大长度是2。

4 Design

设计：问题分析清楚以后，提出解决问题的逻辑框架。

design

  • 输入：表达式“字符串”、输出：“整型”结果。
  • 分层：
    • Expression：将表达式字符串解析成单个字符。
    • DoubleStackProcessor：接收Expression解析出的单个字符进行双栈算法的处理。

5 Implementation

5.1 Instructions

  1. TDD三步军规、小步。
  2. 测试：
    • 始终选择当前最有价值的测试用例；
    • 测试三段式：Arrange、Act、Assert；
    • 不要忘了测试代码也需要重构。
  3. 每次修改代码，都运行一下测试用例，注意红绿绿的节奏。
  4. 写代码应做到：
    • 简洁明了：概念定义清晰、准确；简明清晰地表达语义；
    • 表达到位：层次分明、表现意图；跟问题领域的概念、规则相吻合；
    • 安全可靠：状态、时序管理得当；具有必要的测试安全网络。
  5. 开始写一个测试用例前，先让学员思考如何写测试、如何验证。
  6. 规范(可探讨)：
    • 目录结构：如下所示；
    • 模块名：全小写、多个单词用下划线分隔；
    • 类名：CamelCase、首字母大写、测试类名以Test开头
    • 方法/函数名：全小写、多个单词用下划线分隔，内部方法/函数名以下划线开头。

目录结构

     func
      |- tests
      |    |- __init__.py
      |    |- test_module_a.py
      |    |- test_module_b.py
      |- module_a.py
      |- module_b.py
      |- test_all.py

test_all.py

import unittest

from tests.test_module_a import TestClassA
from tests.test_module_b import TestClassB

if __name__ == '__main__':
    unittest.main()

以module_a为例。

tests.test_module_a.py

import unittest

from module_a import ClassA

class TestClassA(unittest.TestCase):
    ...

module_a.py

class ClassA(object):
    ...

5.2 DoubleStackProcessor

5.2.1 Test Cases

1.  3       (驱动出Operand Stack相关代码)
2.  3+      (驱动出Operator Stack相关代码)
3.  3+2+    (驱动出calc_once和加法计算)
4.  3+2*    (驱动出当前操作符“+”和栈顶操作符“*”的条件判断)
5.  3*2*    (驱动出apply和乘法计算)
6.  3*2+    (测试用例直接测试通过，按照双栈算法描述重构代码)
7.  3+2*3+  (驱动出while{calc_once})
8.  3+2-    (驱动出“-”的优先级映射)
9.  3-2+    (驱动出“-”的计算函数映射)
10. 4-2/    (驱动出“/”的优先级映射)
11. 4/2+    (驱动出“/”的计算函数映射)
12. "3"     (驱动出result pop_operand)
13. "1+2"   (驱动出result if{calc_once})
14. "1+2*3" (驱动出result while{calc_once})

5.2.2 Coding

5.2.2.1 Test Case 1：3

驱动出Operand Stack相关代码。

5.2.2.1.1 Add a Test

新增一个测试用例。要注意：

  • 测试方法名要有含义，能体现测试场景；
  • Wishful Thinking。

test_all.py

import unittest

from tests.test_doublestackprocessor import TestDoubleStackProcessor

if __name__ == '__main__':
    unittest.main()

tests.test_doublestackprocessor.py

import unittest

from doublestackprocessor import DoubleStackProcessor

class TestDoubleStackProcessor(unittest.TestCase):
    def test_num(self):
        dsp = DoubleStackProcessor()

        dsp.process('3')

        self.assertEquals([3], dsp._dump_operandstack())
5.2.2.1.2 Write the Code

添加恰好足够的代码使所有(含新增)测试用例快速通过。要注意：

  • 用最直白的方式让代码尽快通过测试；
  • 测试失败时，注意仔细查看PyUnit的提示，根据提示分析解决问题，不要着急。
  • _operandstack成员变量不想暴露出去，所以以下划线开头。
  • _dump_operandstack()方法仅供测试调用，所以以下划线开头。
  • 产品代码中包含一点点测试辅助代码是可以。在这里，如果不增加_dump_operandstack()方法，就要以别的方式把Operand Stack的数据结构暴露出去，更不好。关于测试辅助代码需要注意几点：
    • 测试辅助代码的逻辑要非常简单，且不能包含业务逻辑。
    • 严格控制测试辅助方法的访问属性。
    • 测试辅助代码尽量少。

doublestackprocessor.py

import copy

class DoubleStackProcessor(object):
    def __init__(self):
        self._operandstack = []

    def process(self, c):
        self._operandstack.append(int(c))

    def _dump_operandstack(self):
        return copy.copy(self._operandstack)
5.2.2.1.3 Refactor the Code

抽取push_operand()方法。

    def process(self, c):
        self.push_operand(int(c))

    def push_operand(self, operand):
        self._operandstack.append(operand)

5.2.2.2 Test Case 2：3+

驱动出Operator Stack相关代码。

5.2.2.2.1 Add a Test
  • _operatorstack成员变量不想暴露出去，所以以下划线开头。
  • _dump_operatorstack()方法仅供测试调用，所以以下划线开头。
    def test_num_plus(self):
        dsp = DoubleStackProcessor()

        dsp.process('3')
        dsp.process('+')

        self.assertEquals([3], dsp._dump_operandstack())
        self.assertEquals(['+'], dsp._dump_operatorstack())
5.2.2.2.2 Write the Code
    def __init__(self):
        self._operandstack = []
        self._operatorstack = []

    def process(self, c):
        if c.isdigit():
            self.push_operand(int(c))
        else:
            self._operatorstack.append(c)

    def _dump_operatorstack(self):
        return copy.copy(self._operatorstack)
5.2.2.2.3 Refactor the Code
  1. 重构产品代码，抽取push_operator()和_dump_stack()方法。
    def process(self, c):
        if c.isdigit():
            self.push_operand(int(c))
        else:
            self.push_operator(c)

    def push_operator(self, operator):
        self._operatorstack.append(operator)

    def _dump_operandstack(self):
        return self._dump_stack(self._operandstack)

    def _dump_operatorstack(self):
        return self._dump_stack(self._operatorstack)

    def _dump_stack(self, stack):
        return copy.copy(stack)
  1. 重构测试代码，增加setUp()方法，将dsp提升为成员变量，在setUp()方法中初始化dsp。
    def setUp(self):
        self.dsp = DoubleStackProcessor()

    def test_num(self):
        self.dsp.process('3')

        self.assertEquals([3], self.dsp._dump_operandstack())

    def test_num_plus(self):
        self.dsp.process('3')
        self.dsp.process('+')

        self.assertEquals([3], self.dsp._dump_operandstack())
        self.assertEquals(['+'], self.dsp._dump_operatorstack())

5.2.2.3 Test Case 3：3+2+

驱动出calc_once和加法计算。

5.2.2.3.1 Add a Test
    def test_num_plus_num_plus(self):
        self.dsp.process('3')
        self.dsp.process('+')
        self.dsp.process('2')
        self.dsp.process('+')        

        self.assertEquals([5], self.dsp._dump_operandstack())
        self.assertEquals(['+'], self.dsp._dump_operatorstack())
5.2.2.3.2 Write the Code
    def process(self, c):
        if c.isdigit():
            self.push_operand(int(c))
        else:
            if len(self._operatorstack) != 0:
                r_operand = self._operandstack.pop()
                l_operand = self._operandstack.pop()
                operator = self._operatorstack.pop()
                self.push_operand(l_operand + r_operand)

            self.push_operator(c)
5.2.2.3.3 Refactor the Code
  1. 抽取not_empty_operatorstack()方法。
    def process(self, c):
        if c.isdigit():
            self.pushOperand(int(c))
        else:
            if self.not_empty_operatorstack():
                rOperand = self._operandStack.pop()
                lOperand = self._operandStack.pop()
                operator = self._operatorStack.pop()
                self.pushOperand(lOperand + rOperand)

            self.pushOperator(c)

    def not_empty_operatorstack(self):
        return len(self._operatorStack) != 0
  1. 抽取calc_once()方法。
    def process(self, c):
        if c.isdigit():
            self.push_operand(int(c))
        else:
            if self.not_empty_operatorstack():
                self.calc_once()

            self.push_operator(c)

    def calc_once(self):
        r_operand = self._operandstack.pop()
        l_operand = self._operandstack.pop()
        operator = self._operatorstack.pop()
        self.push_operand(l_operand + r_operand)
  1. 抽取pop_operand()和pop_operator()方法。
    def calc_once(self):
        r_operand = self.pop_operand()
        l_operand = self.pop_operand()
        operator = self.pop_operator()
        self.push_operand(l_operand + r_operand)

    def pop_operand(self):
        return self._operandstack.pop()

    def pop_operator(self):
        return self._operatorstack.pop()
  1. 抽取process_operator()和process_operand()方法，使代码更清晰并处于同一层次。
    def process(self, c):
        if c.isdigit():
            self.process_operand(c)
        else:
            self.process_operator(c)

    def process_operand(self, c):
        self.push_operand(int(c))

    def process_operator(self, c):
        if self.not_empty_operatorstack():
            self.calc_once()

        self.push_operator(c)

5.2.2.4 Test Case 4：3+2*

驱动出当前操作符“+”和栈顶操作符“*”的条件判断。

5.2.2.4.1 Add a Test
    def test_num_plus_num_multiply(self):
        self.dsp.process('3')
        self.dsp.process('+')
        self.dsp.process('2')
        self.dsp.process('*')        

        self.assertEquals([3, 2], self.dsp._dump_operandstack())
        self.assertEquals(['+', '*'], self.dsp._dump_operatorstack())
5.2.2.4.2 Write the Code
    def process_operator(self, c):
        if self.not_empty_operatorstack():
            if c == '*' and self._operatorstack[-1] == '+':
                pass
            else:
                self.calc_once()

        self.push_operator(c)
5.2.2.4.3 Refactor the Code

抽取top_operator()方法。

    def process_operator(self, c):
        if self.not_empty_operatorstack():
            if c == '*' and self.top_operator() == '+':
                pass
            else:
                self.calc_once()

        self.push_operator(c)

    def top_operator(self):
        return self._operatorstack[-1]

5.2.2.5 Test Case 5：3*2*

驱动出apply和乘法计算。

5.2.2.5.1 Add a Test
    def test_num_multiply_num_multiply(self):
        self.dsp.process('3')
        self.dsp.process('*')
        self.dsp.process('2')
        self.dsp.process('*')
        
        self.assertEquals([6], self.dsp._dump_operandstack())
        self.assertEquals(['*'], self.dsp._dump_operatorstack())
5.2.2.5.2 Write the Code
    def calc_once(self):
        r_operand = self.pop_operand()
        l_operand = self.pop_operand()
        operator = self.pop_operator()
        if '+' == operator:
            result = l_operand + r_operand
        elif '*' == operator:
            result = l_operand * r_operand
        else:
            result = 0 # Temporarily
        self.push_operand(result)
5.2.2.5.3 Refactor the Code
  1. 抽取apply()方法。
    def calc_once(self):
        r_operand = self.pop_operand()
        l_operand = self.pop_operand()
        operator = self.pop_operator()
        self.push_operand(self.apply(operator, l_operand, r_operand))

    def apply(self, operator, l_operand, r_operand):
        if '+' == operator:
            result = l_operand + r_operand
        elif '*' == operator:
            result = l_operand * r_operand
        else:
            result = 0 # temporarily
        return result
  1. 改进apply()方法内部实现。定义一个操作符和操作函数的映射。
class DoubleStackProcessor(object):
    operator_func_map = {'+':lambda x, y: x + y,
                         '*':lambda x, y: x * y}

    def apply(self, operator, l_operand, r_operand):
        return DoubleStackProcessor.operator_func_map[operator](l_operand, r_operand)

5.2.2.6 Test Case 6：3*2+

测试用例直接测试通过，按照双栈算法描述重构代码。

5.2.2.6.1 Add a Test

以目前的产品代码，这个测试用例是可以直接测试通过的。

    def test_num_multiply_num_plus(self):
        self.dsp.process('3')
        self.dsp.process('*')
        self.dsp.process('2')
        self.dsp.process('+')
        
        self.assertEquals([6], self.dsp._dump_operandstack())
        self.assertEquals(['+'], self.dsp._dump_operatorstack())
5.2.2.6.2 Write the Code

无。

5.2.2.6.3 Refactor the Code

双栈算法描述中有一句话：如果操作符栈不为空且当前操作符的优先级不高于栈顶操作符优先级时，计算一次。按照双栈算法描述重构process_operator()方法。

定义一个操作符和优先级的映射，将操作符优先级的比较转化为数的大小比较。

    operator_priority_map = {'+':1, '*':2}

    def process_operator(self, c):
        if self.not_empty_operatorstack() and self.not_prior_to(c, self.top_operator()):
            self.calc_once()

        self.push_operator(c)

    def not_prior_to(self, operator1, operator2):
        return DoubleStackProcessor.operator_priority_map[operator1] \
                <= DoubleStackProcessor.operator_priority_map[operator2]

继续改进not_prior_to()方法。

    def not_prior_to(self, operator1, operator2):
        return self.priority(operator1) <= self.priority(operator2)

    def priority(self, operator):
        return DoubleStackProcessor.operator_priority_map[operator]

5.2.2.7 Test Case 7：3+2*3+

驱动出while{calc_once}。

5.2.2.7.1 Add a Test
    def test_num_plus_num_multiply_num_plus(self):
        self.dsp.process('3')
        self.dsp.process('+')
        self.dsp.process('2')
        self.dsp.process('*')
        self.dsp.process('3')
        self.dsp.process('+')
        
        self.assertEquals([9], self.dsp._dump_operandstack())
        self.assertEquals(['+'], self.dsp._dump_operatorstack())
5.2.2.7.2 Write the Code
    def process_operator(self, c):
        while self.not_empty_operatorstack() and self.not_prior_to(c, self.top_operator()):
            self.calc_once()

        self.push_operator(c)
5.2.2.7.3 Refactor the Code

无。

5.2.2.8 Test Case 8：3+2-

驱动出“-”的优先级映射。

5.2.2.8.1 Add a Test
    def test_num_plus_num_subtract(self):
        self.dsp.process('3')
        self.dsp.process('+')
        self.dsp.process('2')
        self.dsp.process('-')
        
        self.assertEquals([5], self.dsp._dump_operandstack())
        self.assertEquals(['-'], self.dsp._dump_operatorstack())
5.2.2.8.2 Write the Code
    operator_priority_map = {'+':1, '-':1, '*':2}
5.2.2.8.3 Refactor the Code

无。

5.2.2.9 Test Case 9：3-2+

驱动出“-”的计算函数映射。

5.2.2.9.1 Add a Test
    def test_num_subtract_num_plus(self):
        self.dsp.process('3')
        self.dsp.process('-')
        self.dsp.process('2')
        self.dsp.process('+')
        
        self.assertEquals([1], self.dsp._dump_operandstack())
        self.assertEquals(['+'], self.dsp._dump_operatorstack())
5.2.2.9.2 Write the Code
    operator_func_map = {'+':lambda x, y: x + y,
                         '-':lambda x, y: x - y,
                         '*':lambda x, y: x * y}
5.2.2.9.3 Refactor the Code

无。

5.2.2.10 Test Case 10：4-2/

驱动出“/”的优先级映射。

5.2.2.10.1 Add a Test
    def test_num_subtract_num_divide(self):
        self.dsp.process('4')
        self.dsp.process('-')
        self.dsp.process('2')
        self.dsp.process('/')
        
        self.assertEquals([4, 2], self.dsp._dump_operandstack())
        self.assertEquals(['-', '/'], self.dsp._dump_operatorstack())
5.2.2.10.2 Write the Code
    operator_priority_map = {'+':1, '-':1, '*':2, '/':2}
5.2.2.10.3 Refactor the Code

无。

5.2.2.11 Test Case 11：4/2+

驱动出“/”的计算函数映射。

5.2.2.11.1 Add a Test
    def test_num_divide_num_plus(self):
        self.dsp.process('4')
        self.dsp.process('/')
        self.dsp.process('2')
        self.dsp.process('+')
        
        self.assertEquals([2], self.dsp._dump_operandstack())
        self.assertEquals(['+'], self.dsp._dump_operatorstack())
5.2.2.11.2 Write the Code
    operator_func_map = {'+':lambda x, y: x + y,
                         '-':lambda x, y: x - y,
                         '*':lambda x, y: x * y,
                         '/':lambda x, y: x / y}
5.2.2.11.3 Refactor the Code

无。

5.2.2.12 Test Case 12："3"

DoubleStackProcessor需要为Expression提供一个获取双栈算法最终处理结果的result()方法。根据双栈算法，当表达式解析到结尾以后，双栈会有三种状态：

  • 第一种状态：操作符栈为空，操作数栈只有一个操作数。这是最简单的一种状态，只需要从操作数栈中pop出这个操作数即可，双栈最终均为空。
  • 第二种状态：操作符栈有一个操作符，操作数栈有两个操作数。这时，只需要做一次calc_once，双栈状态就变成了第一种状态，只需要从操作数栈中pop出这个操作数即可，双栈最终均为空。
  • 第三种状态：操作符栈有两个操作符，操作数栈有三个操作数。这时，做两次calc_once，双栈状态就变成了第一种状态，只需要从操作数栈中pop出这个操作数即可，双栈最终均为空。

先来处理第一种状态，驱动出result()方法。

5.2.2.12.1 Add a Test
    def test_result_num(self):
        self.dsp.process('3')

        self.assertEquals(3, self.dsp.result())
        self.assertEquals([], self.dsp._dump_operandstack())
        self.assertEquals([], self.dsp._dump_operatorstack())
5.2.2.12.2 Write the Code
    def result(self):
        return self.pop_operand()
5.2.2.12.3 Refactor the Code

无。

5.2.2.13 Test Case 13："1+2"

再来处理第二种状态，驱动出result()方法中的if{calc_once}。

5.2.2.13.1 Add a Test
    def test_result_calc_once(self):
        self.dsp.process('1')
        self.dsp.process('+')
        self.dsp.process('2')

        self.assertEquals(3, self.dsp.result())
        self.assertEquals([], self.dsp._dump_operandstack())
        self.assertEquals([], self.dsp._dump_operatorstack())
5.2.2.13.2 Write the Code
    def result(self):
        if self.not_empty_operatorstack():
            self.calc_once()
        
        return self.pop_operand()
5.2.2.13.3 Refactor the Code

抽取calc()方法。

    def result(self):
        self.calc()
        return self.pop_operand()

    def calc(self):
        if self.not_empty_operatorstack():
            self.calc_once()

5.2.2.14 Test Case 14："1+2*3"

最后处理第三种状态，驱动出result()方法中的while{calc_once}。

5.2.2.14.1 Add a Test
    def test_result_calc_twice(self):
        self.dsp.process('1')
        self.dsp.process('+')
        self.dsp.process('2')
        self.dsp.process('*')
        self.dsp.process('3')

        self.assertEquals(7, self.dsp.result())
        self.assertEquals([], self.dsp._dump_operandstack())
        self.assertEquals([], self.dsp._dump_operatorstack())
5.2.2.14.2 Write the Code

将calc()方法中的if改为while。

    def calc(self):
        while self.not_empty_operatorstack():
            self.calc_once()
5.2.2.14.3 Refactor the Code

无。

5.3 Expression

5.3.1 Test Cases

1. "3"       (驱动出Expression的主体代码)
2. "2*(1+2)" (驱动出Context和括号相关的代码)

5.3.2 Coding

5.3.2.1 Test Case 1："3"

驱动出Expression的主体代码。

5.3.2.1.1 Add a Test

因为最终要实现括号相关的需求，括号中间的表达式称为“子表达式”。无论是表达式还是子表达式都应该拥有各自的Expression对象。所以将表达式字符串作为Expression的构造参数。

test_all.py

import unittest

from tests.test_doublestackprocessor import TestDoubleStackProcessor
from tests.test_expression import TestExpression

if __name__ == '__main__':
    unittest.main()

test_expression.py

import unittest

from expression import Expression

class TestExpression(unittest.TestCase):
    def test_num(self):
        expr = Expression("3")
        self.assertEquals(3, expr.eval())
5.3.2.1.2 Write the Code

从构造函数传入的表达式字符串expr作为Expression的成员变量。每个表达式或子表达式都应该拥有自己的DoubleStackProcessor对象实例，所以DoubleStackProcessor dsp对象实例也作为Expression的成员变量。另外，还需要记住读取表达式字符串的当前位置，所以curidx也作为Expression的成员变量。

expression.py

from doublestackprocessor import DoubleStackProcessor

class Expression(object):
    def __init__(self, expr):
        self.expr = expr
        self.curidx = 0
        self.dsp = DoubleStackProcessor()

    def eval(self):
        while self.curidx < len(self.expr):
            self.dsp.process(self.expr[self.curidx])
            self.curidx += 1

        return self.dsp.result()
5.3.2.1.3 Refactor the Code
  1. 抽取expr_not_end()方法。
    def eval(self):
        while self.expr_not_end():
            self.dsp.process(self.expr[self.curidx])
            self.curidx += 1

        return self.dsp.result()

    def expr_not_end(self):
        return self.curidx < len(self.expr)
  1. 抽取next_char()方法。
    def eval(self):
        while self.expr_not_end():
            self.dsp.process(self.next_char())

        return self.dsp.result()

    def next_char(self):
        c = self.expr[self.curidx]
        self.curidx += 1
        return c

5.3.2.2 Test Case 2："2*(1+2)"

驱动出Context和括号相关的代码。

5.3.2.2.1 Add a Test (Context)
    def test_expr_has_parentheses(self):
        expr = Expression("2*(1+2)")
        self.assertEquals(6, expr.eval())

表达式中有括号就意味着表达式可以嵌套，实现中肯定会包含递归调用。
首先，在整个递归调用中，需要一直准确地记录读取表达式字符串的当前位置(curidx)。但在Python语言中数值型的curidx是无法在递归调用中传递的，所以引入一个Context对象，包含curidx。
其次，递归调用时Expression的构造方法肯定要传入子表达式字符串(expr)，所以把expr和curidx封装为Context对象。

暂时注释掉上面的括号相关的测试用例，增加Context相关的测试用例。

from expression import Expression, Context

    def test_expr_context(self):
        expr = Expression(None, Context("3", 0))
        self.assertEquals(3, expr.eval())
5.3.2.2.2 Write the Code (Context)

增加Context类。

class Context(object):
    def __init__(self, expr, curidx):
        self.expr = expr
        self.curidx = curidx

根据《重构》中的“依恋情结”章节的描述，如果某个类的某段代码中引用的所有变量或方法都来自于另一个类，意味着这段代码放在那个类中更合适。据此，将Expression类中的expr_not_end()和next_char()挪到Context类中。

class Context(object):
    def __init__(self, expr, curidx):
        self.expr = expr
        self.curidx = curidx

    def expr_not_end(self):
        return self.curidx < len(self.expr)

    def next_char(self):
        c = self.expr[self.curidx]
        self.curidx += 1
        return c

围绕Context修改Expression类。

class Expression(object):
    def __init__(self, expr, context=None):
        if context == None:
            self.ctx = Context(expr, 0)
        else:
            self.ctx = context

        self.dsp = DoubleStackProcessor()

    def eval(self):
        while self.ctx.expr_not_end():
            self.dsp.process(self.ctx.next_char())

        return self.dsp.result()

Expression类的__init__()之所以这样写，是因为Expression类需要对外提供两种构造参数形式，一种是expr字符串，一种是context。

5.3.2.2.3 Refactor the Code (Context)

无。

5.3.2.2.4 Add a Test (Parentheses)

放开之前注释的括号相关的测试用例。

    def test_expr_has_parentheses(self):
        expr = Expression("2*(1+2)")
        self.assertEquals(6, expr.eval())
5.3.2.2.5 Write the Code (Parentheses)

修改Expression类的eval()方法。

  • 当前字符为“(”时，说明接下来是一个子表达式，把上下文ctx传给子表达式对应的新的Expression对象，eval()出的结果是子表达式的计算结果，入当前表达式操作数栈。
  • 当前字符为“)”时，说明子表达式即将结束，此时的dsp是子表达式的dsp，调用dsp.result()得到子表达式的计算结果并返回。
  • 其他情况下，属于一个表达式内部处理，交给自己的dsp处理即可。
  • 代码看上去是平面的，但运行起来是立体的，注意仔细体会。
    def eval(self):
        while self.ctx.expr_not_end():
            c = self.ctx.next_char()
            if '(' == c:
                self.dsp.push_operand(Expression(self.ctx.expr, self.ctx).eval())
            elif ')' == c:
                return self.dsp.result()
            else:
                self.dsp.process(c)

        return self.dsp.result()
5.3.2.2.6 Refactor the Code (Parentheses)

无。

5.3.2.3 Final Test Cases

至此四则运算的代码已全部实现。这里只是用一些复杂的测试用例验证一下。

    def test_expr_final(self):
        expr = Expression("((1+2)+1)*2")
        self.assertEquals(8, expr.eval())
        
        expr = Expression("(1+(1+2))*2")
        self.assertEquals(8, expr.eval())
                
        expr = Expression("(2-(1-2))*3+(2-(2+1))*3")
        self.assertEquals(6, expr.eval())

6 Summary

请学员先总结一下。

  1. TDD三步军规、小步。
  2. 测试：
    • 始终选择当前最有价值的测试用例；
    • 测试三段式：Arrange、Act、Assert；
    • 不要忘了测试代码也需要重构。
  3. 每次修改代码，都运行一下测试用例，注意红绿绿的节奏。
  4. 写代码应做到：
    • 简洁明了：概念定义清晰、准确；简明清晰地表达语义；
    • 表达到位：层次分明、表现意图；跟问题领域的概念、规则相吻合；
    • 安全可靠：状态、时序管理得当；具有必要的测试安全网络。
  5. 规范
    • 目录结构；
    • 模块名；
    • 类名；
    • 方法/函数名。

代码路径：oo.original

7 Homework

  1. 【必选】表达式支持“取余”操作符“%”，优先级与“*、/”一样。
  2. 【可选】表达式支持多位正整数。
  3. 【必选】表达式支持“幂”操作符“**”，优先级比“*、/”高。
  4. 【可选】表达式支持负整数。

8 My Homework

8.1 Rem

表达式支持“取余”操作符“%”，优先级与“*、/”一样。

代码路径：oo.rem

8.1.1 Test Cases

测试用例如下：

15. 3+2% (驱动出“%”的优先级映射)
16. 3%2+ (驱动出“%”的计算函数映射)

8.1.2 Coding

8.1.2.1 Test Case 15：3+2rem

驱动出“%”的优先级映射。

8.1.2.1.1 Add a Test

tests.test_doublestackprocessor.py

def test_num_plus_num_rem(self):
        self.dsp.process('3')
        self.dsp.process('+')
        self.dsp.process('2')
        self.dsp.process('%')
        
        self.assertEquals([3, 2], self.dsp._dump_operandstack())
        self.assertEquals(['+', '%'], self.dsp._dump_operatorstack())
8.1.2.1.2 Write the Code

doublestackprocessor.py

    operator_priority_map = {'+':1, '-':1, '*':2, '/':2, '%':2}
8.1.2.1.3 Refactor the Code

无。

8.1.2.2 Test Case 16：3rem2+

驱动出“%”的计算函数映射。

8.1.2.2.1 Add a Test

tests.test_doublestackprocessor.py

    def test_num_rem_num_plus(self):
        self.dsp.process('3')
        self.dsp.process('%')
        self.dsp.process('2')
        self.dsp.process('+')
        
        self.assertEquals([1], self.dsp._dump_operandstack())
        self.assertEquals(['+'], self.dsp._dump_operatorstack())
8.1.2.2.2 Write the Code

doublestackprocessor.py

    operator_func_map = {'+':lambda x, y: x + y,
                         '-':lambda x, y: x - y,
                         '*':lambda x, y: x * y,
                         '/':lambda x, y: x / y,
                         '%':lambda x, y: x % y}
8.1.2.2.3 Refactor the Code

无。

8.2 Multi-digit Positive Integer

表达式支持多位正整数。

代码路径：oo.multidigit

由Expression类完成“多位正整数”操作数的解析。
DoubleStackProcessor类的process()方法不能只接受一个字符，改为接受字符串。

先后分别修改DoubleStackProcessor和Expression的测试代码和产品代码。

8.2.1 DoubleStackProcessor

8.2.1.1 Test Cases

为了做到小步，先把TestDoubleStackProcessor类中原有的测试用例方法名都加“_2”，等全部改好了以后，再删掉这些不再有用的测试用例。

测试用例如下：

1.  12         (新增process(item)方法)
2.  12+        (process(item)增加isdigit判断分支)  
3.  12+34+     (新增process_operand(item)和process_operator(item)方法。
                其中process_operator()中增加操作符栈是否为空的判断分支。)
4.  12+34*     (process_operator()方法增加not_prior_to()判断分支。)
5.  12*10*     (测试用例直接测试通过)
6.  12*10+     (测试用例直接测试通过)
7.  12+34-     (测试用例直接测试通过)
8.  34-12+     (测试用例直接测试通过)
9.  34-12/     (测试用例直接测试通过)
10. 24/12+     (测试用例直接测试通过)
11. 12+34%     (测试用例直接测试通过)
12. 34%12+     (测试用例直接测试通过)
13. 12+10*34+  (驱动出while{calc_once})
14. "12"       (测试用例直接测试通过)
15. "12+34"    (测试用例直接测试通过)
16. "12+34*10" (测试用例直接测试通过)

8.2.1.2 Coding

8.2.1.2.1 Test Case 1：12
8.2.1.2.1.1 Add a Test

把DoubleStackProcessor类中的process(c)方法重命名为process_2(c)。TestDoubleStackProcessor类、Expression类中调用process(c)方法的地方也全部改为调用process_2(c)。

新增process(item)方法，等全部改好了以后，再删掉process_2(c)方法。这样对Expression的影响也比较小。

def test_num(self):
        self.dsp.process('12')

        self.assertEquals([12], self.dsp._dump_operandstack())
8.2.1.2.1.2 Write the Code

新增process(item)方法。

    def process(self, item):
        self.push_operand(int(item))
8.2.1.2.1.3 Refactor the Code

无。

8.2.1.2.2 Test Case 2：12+
8.2.1.2.2.1 Add a Test
    def test_num_plus(self):
        self.dsp.process('12')
        self.dsp.process('+')

        self.assertEquals([12], self.dsp._dump_operandstack())
        self.assertEquals(['+'], self.dsp._dump_operatorstack())
8.2.1.2.2.2 Write the Code

process(item)方法增加isdigit判断分支。

    def process(self, item):
        if item.isdigit():
            self.push_operand(int(item))
        else:
            self.push_operator(item)
8.2.1.2.2.3 Refactor the Code

无。

8.2.1.2.3 Test Case 3：12+34+
8.2.1.2.3.1 Add a Test
    def test_num_plus_num_plus(self):
        self.dsp.process('12')
        self.dsp.process('+')
        self.dsp.process('34')
        self.dsp.process('+')

        self.assertEquals([46], self.dsp._dump_operandstack())
        self.assertEquals(['+'], self.dsp._dump_operatorstack())
8.2.1.2.3.2 Write the Code

将process_operand(c)重命名为process_operand_2(c)，将process_operator(c)重命名为process_operator_2(c)。

新增process_operand(item)和process_operator(item)方法，等全部改好了以后，再删掉process_operand_2(c)和process_operator_2(c)方法。其中process_operator()中增加操作符栈是否为空的判断分支。

    def process(self, item):
        if item.isdigit():
            self.process_operand(item)
        else:
            self.process_operator(item)

    def process_operand(self, item):
        self.push_operand(int(item))

    def process_operator(self, item):
        if self.not_empty_operatorstack():
            self.calc_once()

        self.push_operator(item)
8.2.1.2.3.3 Refactor the Code

无。

8.2.1.2.4 Test Case 4：12+34*
8.2.1.2.4.1 Add a Test
    def test_num_plus_num_multiply(self):
        self.dsp.process('12')
        self.dsp.process('+')
        self.dsp.process('34')
        self.dsp.process('*')        

        self.assertEquals([12, 34], self.dsp._dump_operandstack())
        self.assertEquals(['+', '*'], self.dsp._dump_operatorstack())
8.2.1.2.4.2 Write the Code

process_operator()方法增加not_prior_to()判断分支。

    def process_operator(self, item):
        if self.not_empty_operatorstack() and self.not_prior_to(item, self.top_operator()):
            self.calc_once()

        self.push_operator(item)
8.2.1.2.4.3 Refactor the Code

无。

8.2.1.2.5 Test Case 5-12

到这里，以下测试用例全部可以直接测试通过。

5.  12*10*
6.  12*10+
7.  12+34-
8.  34-12+
9.  34-12/
10. 24/12+
11. 12+34%
12. 34%12+

    def test_num_multiply_num_multiply(self):
        self.dsp.process('12');
        self.dsp.process('*');
        self.dsp.process('10');
        self.dsp.process('*');
        
        self.assertEquals([120], self.dsp._dump_operandstack());
        self.assertEquals(['*'], self.dsp._dump_operatorstack());
    
    def test_num_multiply_num_plus(self):
        self.dsp.process('12');
        self.dsp.process('*');
        self.dsp.process('10');
        self.dsp.process('+');
        
        self.assertEquals([120], self.dsp._dump_operandstack());
        self.assertEquals(['+'], self.dsp._dump_operatorstack());
    
    def test_num_plus_num_subtract(self):
        self.dsp.process('12');
        self.dsp.process('+');
        self.dsp.process('34');
        self.dsp.process('-');
        
        self.assertEquals([46], self.dsp._dump_operandstack());
        self.assertEquals(['-'], self.dsp._dump_operatorstack());

    def test_num_subtract_num_plus(self):
        self.dsp.process('34');
        self.dsp.process('-');
        self.dsp.process('12');
        self.dsp.process('+');
        
        self.assertEquals([22], self.dsp._dump_operandstack());
        self.assertEquals(['+'], self.dsp._dump_operatorstack());
    
    def test_num_subtract_num_divide(self):
        self.dsp.process('34');
        self.dsp.process('-');
        self.dsp.process('12');
        self.dsp.process('/');
        
        self.assertEquals([34, 12], self.dsp._dump_operandstack());
        self.assertEquals(['-', '/'], self.dsp._dump_operatorstack());
    
    def test_num_divide_num_plus(self):
        self.dsp.process('24');
        self.dsp.process('/');
        self.dsp.process('12');
        self.dsp.process('+');
        
        self.assertEquals([2], self.dsp._dump_operandstack());
        self.assertEquals(['+'], self.dsp._dump_operatorstack());
    
    def test_num_plus_num_rem(self):
        self.dsp.process('12');
        self.dsp.process('+');
        self.dsp.process('34');
        self.dsp.process('%');
        
        self.assertEquals([12, 34], self.dsp._dump_operandstack());
        self.assertEquals(['+', '%'], self.dsp._dump_operatorstack());
    
    def test_num_rem_num_plus(self):
        self.dsp.process('34');
        self.dsp.process('%');
        self.dsp.process('12');
        self.dsp.process('+');
                
        self.assertEquals([10], self.dsp._dump_operandstack());
        self.assertEquals(['+'], self.dsp._dump_operatorstack());
8.2.1.2.6 Test Case 13：12+10*34+
8.2.1.2.6.1 Add a Test
    def test_num_plus_num_multiply_num_plus(self):
        self.dsp.process('12')
        self.dsp.process('+')
        self.dsp.process('10')
        self.dsp.process('*')
        self.dsp.process('34')
        self.dsp.process('+')
        
        self.assertEquals([352], self.dsp._dump_operandstack())
        self.assertEquals(['+'], self.dsp._dump_operatorstack())
8.2.1.2.6.2 Write the Code

驱动出while{calc_once}。

    def process_operator(self, item):
        while self.not_empty_operatorstack() and self.not_prior_to(item, self.top_operator()):
            self.calc_once()

        self.push_operator(item)
8.2.1.2.6.3 Refactor the Code

无。

8.2.1.2.7 Test Case 14-16

到这里，以下测试用例全部可以直接测试通过。

14. "12"
15. "12+34"
16. "12+34*10"

    def test_result_num(self):
        self.dsp.process('12')

        self.assertEquals(12, self.dsp.result())
        self.assertEquals([], self.dsp._dump_operandstack())
        self.assertEquals([], self.dsp._dump_operatorstack())

    def test_result_calc_once(self):
        self.dsp.process('12')
        self.dsp.process('+')
        self.dsp.process('34')

        self.assertEquals(46, self.dsp.result())
        self.assertEquals([], self.dsp._dump_operandstack())
        self.assertEquals([], self.dsp._dump_operatorstack())

    def test_result_calc_twice(self):
        self.dsp.process('12')
        self.dsp.process('+')
        self.dsp.process('34')
        self.dsp.process('*')
        self.dsp.process('10')

        self.assertEquals(352, self.dsp.result())
        self.assertEquals([], self.dsp._dump_operandstack())
        self.assertEquals([], self.dsp._dump_operatorstack())
8.2.1.2.8 Delete All Useless TestCases

删除TestDoubleStackProcessor类中所有不再有用的测试用例，即方法名以“_2”结尾的测试用例。

由于Expression类尚未修改，DoubleStackProcess类中的process_2(c)方法暂时不能删除。

8.2.2 Expression

8.2.2.1 Test Cases

为了做到小步，先把TestExpression类中原有的测试用例方法名都加“_2”，等全部改好了以后，再删掉这些不再有用的测试用例。同时，把Expression类原有的eval()方法改名为eval_2()。

测试用例如下：

1.  "12"          (驱动出eval()中的数字缓存逻辑)
2.  "12+34"       (eval()中增加字符是数字或操作符号的判断分支)
3.  "12+34*10"    (测试用例直接测试通过)
4.  "(12+34)*10"  (eval()中增加右括号后面紧跟着操作符的处理逻辑)
5.  "10*(12+34)"  (eval()中增加表达式以右括号结尾的处理逻辑)
6.  "(48-(12+34))*10" "10*(48-(12+34))"  (eval()中增加右括号紧跟右括号的处理逻辑)

8.2.2.2 Coding

8.2.2.2.1 Test Case 1："12"

驱动出eval()中的数字缓存逻辑。

8.2.2.2.1.1 Add a Test
    def test_num(self):
        expr = Expression("12")
        self.assertEquals(12, expr.eval())
8.2.2.2.1.2 Write the Code
    def eval(self):
        digitbuffer = ''

        while self.ctx.expr_not_end():
            digitbuffer += self.ctx.next_char()

        self.dsp.process(digitbuffer)
        return self.dsp.result()
8.2.2.2.1.3 Refactor the Code

无。

8.2.2.2.2 Test Case 2："12+34"

eval()中增加字符是数字或操作符号的判断分支。

8.2.2.2.2.1 Add a Test
    public void test_expr_has_one_operator()
    {
        Expression expr = new Expression("12+34");
        assertEquals(46, expr.eval());
    }
8.2.2.2.2.2 Write the Code

操作数出现在操作符之前和表达式结尾。

    def eval(self):
        digitbuffer = ''

        while self.ctx.expr_not_end():
            c = self.ctx.next_char()
            if c.isdigit():
                digitbuffer += c
            else:
                self.dsp.process(digitbuffer)
                digitbuffer = ''

                self.dsp.process(c)

        self.dsp.process(digitbuffer)
        return self.dsp.result()
8.2.2.2.2.3 Refactor the Code

无。

8.2.2.2.3 Test Case 3："12+34*10"
8.2.2.2.3.1 Add a Test

以目前的产品代码，这个测试用例是可以直接测试通过的。

    def test_expr_has_multiple_operators(self):
        expr = Expression("12+34*10")
        self.assertEquals(352, expr.eval())
8.2.2.2.3.2 Write the Code

无。

8.2.2.2.3.3 Refactor the Code

无。

8.2.2.2.4 Test Case 4："(12+34)*10"

eval()中增加右括号后面紧跟着操作符的处理逻辑。此时digitbuffer长度为0。

操作数除了出现在操作符之前和表达式结尾，还可以出现在子表达式结尾，即“)”之前。

8.2.2.2.4.1 Add a Test
    def test_expr_with_right_parenthesis_followed_by_an_operator(self):
        expr = Expression("(12+34)*10")
        self.assertEquals(460, expr.eval())
8.2.2.2.4.2 Write the Code
    def eval(self):
        digitbuffer = ''

        while self.ctx.expr_not_end():
            c = self.ctx.next_char()
            if '(' == c:
                self.dsp.push_operand(Expression(self.ctx.expr, self.ctx).eval())
            elif ')' == c:
                self.dsp.process(digitbuffer)
                return self.dsp.result()
            else:
                if c.isdigit():
                    digitbuffer += c
                else:
                    if len(digitbuffer) != 0: # else len(digitbuffer) == 0 when right parenthesis followed by an operator
                        self.dsp.process(digitbuffer)
                        digitbuffer = ''

                    self.dsp.process(c)

        self.dsp.process(digitbuffer)
        return self.dsp.result()
8.2.2.2.4.3 Refactor the Code

无。

8.2.2.2.5 Test Case 5："10*(12+34)"

eval()中增加表达式以右括号结尾的处理逻辑。此时digitbuffer长度为0。

8.2.2.2.5.1 Add a Test
    def test_expr_ends_with_right_parenthesis(self):
        expr = Expression("10*(12+34)")
        self.assertEquals(460, expr.eval())
8.2.2.2.5.2 Write the Code
    def eval(self):
        digitbuffer = ''

        while self.ctx.expr_not_end():
            c = self.ctx.next_char()
            if '(' == c:
                self.dsp.push_operand(Expression(self.ctx.expr, self.ctx).eval())
            elif ')' == c:
                self.dsp.process(digitbuffer)
                return self.dsp.result()
            else:
                if c.isdigit():
                    digitbuffer += c
                else:
                    if len(digitbuffer) != 0: # else len(digitbuffer) == 0 when right parenthesis followed by an operator
                        self.dsp.process(digitbuffer)
                        digitbuffer = ''

                    self.dsp.process(c)

        if len(digitbuffer) != 0:
            self.dsp.process(digitbuffer) # else len(digitbuffer) == 0 when expr ends with right parenthesis

        return self.dsp.result()
8.2.2.2.5.3 Refactor the Code

无。

8.2.2.2.6 Test Case 6："(48-(12+34))*10"、"10*(48-(12+34))"

eval()中增加右括号紧跟右括号的处理逻辑。此时digitbuffer长度为0。

8.2.2.2.6.1 Add a Test
    def test_expr_with_right_parenthesis_followed_by_right_parenthesis(self):
        expr = Expression("(48-(12+34))*10")
        self.assertEquals(20, expr.eval())
        
        expr = Expression("10*(48-(12+34))")
        self.assertEquals(20, expr.eval())
8.2.2.2.6.2 Write the Code
    def eval(self):
        digitbuffer = ''

        while self.ctx.expr_not_end():
            c = self.ctx.next_char()
            if '(' == c:
                self.dsp.push_operand(Expression(self.ctx.expr, self.ctx).eval())
            elif ')' == c:
                if len(digitbuffer) != 0: # else len(digitbuffer) == 0 when right parenthesis followed by right parenthesis
                    self.dsp.process(digitbuffer)
                    
                return self.dsp.result()
            else:
                if c.isdigit():
                    digitbuffer += c
                else:
                    if len(digitbuffer) != 0: # else len(digitbuffer) == 0 when right parenthesis followed by an operator
                        self.dsp.process(digitbuffer)
                        digitbuffer = ''

                    self.dsp.process(c)

        if len(digitbuffer) != 0:
            self.dsp.process(digitbuffer) # else len(digitbuffer) == 0 when expr ends with right parenthesis

        return self.dsp.result()
8.2.2.2.6.3 Refactor the Code

无。

8.2.2.2.7 Final Test Cases

至此多位正整数相关代码已全部实现。这里只是用一些复杂的测试用例验证一下。

    def test_expr_with_nested_parentheses(self):
        expr = Expression("((10+21)+34)*20")
        self.assertEquals(1300, expr.eval())
        
        expr = Expression("(50-(12+34))*20")
        self.assertEquals(80, expr.eval())
        
        expr = Expression("((11+23)%11)*20")
        self.assertEquals(20, expr.eval())
                
        expr = Expression("(12-(15-12))*10/(24-(12+10))/3")
        self.assertEquals(15, expr.eval())
        
        expr = Expression("(100-(1920-1900))*2/(24-(12+10))/2")
        self.assertEquals(40, expr.eval())
8.2.2.2.8 Delete All Useless TestCases and Product Code

先删除TestExpression类中所有不再有用的测试用例，即方法名以“_2”结尾的测试用例。
再删除Expression、DoubleStackProcess类中所有不再有用的产品代码。

8.3 Pow **

表达式支持“幂”操作符“**”，优先级比“*、/”高。

代码路径：oo.pow

由Expression类完成类似“**”这种字符长度超过1的操作符的解析。

8.3.1 DoubleStackProcessor

支持“幂”操作符“**”。

8.3.1.1 Test Cases

测试用例如下：

17. 12*2**  (驱动出“**”的优先级映射)
18. 10**3*  (驱动出“**”的计算函数映射)

8.3.1.2 Coding

8.3.1.2.1 Test Case 17：12*2**

驱动出“**”的优先级映射。

8.3.1.2.1 Add a Test
    def test_num_multiply_num_pow(self):
        self.dsp.process('12');
        self.dsp.process('*');
        self.dsp.process('2');
        self.dsp.process('**');
        
        self.assertEquals([12, 2], self.dsp._dump_operandstack())
        self.assertEquals(['*', '**'], self.dsp._dump_operatorstack())
8.3.1.2.2 Write the Code
    operator_priority_map = {'+':1, '-':1, '*':2, '/':2, '%':2, '**':3}
8.3.1.2.3 Refactor the Code

无。

8.3.1.2.2 Test Case 18：10**3*

驱动出“**”的计算函数映射。

8.3.1.2.2.1 Add a Test
    def test_num_pow_num_multiply(self):
        self.dsp.process('10');
        self.dsp.process('**');
        self.dsp.process('3');
        self.dsp.process('*');
        
        self.assertEquals([1000], self.dsp._dump_operandstack())
        self.assertEquals(['*'], self.dsp._dump_operatorstack())
8.3.1.2.2.2 Write the Code
    operator_func_map = {'+':lambda x, y: x + y,
                         '-':lambda x, y: x - y,
                         '*':lambda x, y: x * y,
                         '/':lambda x, y: x / y,
                         '%':lambda x, y: x % y,
                         '**':lambda x, y: x ** y}
8.3.1.2.2.3 Refactor the Code

无。

8.3.2 Expression

完成类似“**”这种字符长度超过1的操作符的解析。

8.3.2.1 Test Cases

测试用例如下：

7. "2**3"      (驱动出eval()中的操作符字符缓存逻辑以及操作符后面紧跟着数字的处理逻辑)
8. "2**(1+2)"  (eval()中增加操作符后面紧跟着左括号的处理逻辑)

8.3.2.2 Coding

8.3.2.2.1 Test Case 7："2**3"

驱动出eval()中的操作符字符缓存逻辑。

8.3.2.2.1.1 Add a Test
    def test_expr_with_pow(self):
        expr = Expression("2**3");
        self.assertEquals(8, expr.eval());
8.3.2.2.1.2 Write the Code

操作符后紧跟着数字。

    def eval(self):
        digitbuffer = ''
        operatorbuffer = ''

        while self.ctx.expr_not_end():
            c = self.ctx.next_char()
            if '(' == c:
                self.dsp.push_operand(Expression(self.ctx.expr, self.ctx).eval())
            elif ')' == c:
                if len(digitbuffer) != 0: # else len(digitbuffer) == 0 when right parenthesis followed by right parenthesis
                    self.dsp.process(digitbuffer)

                return self.dsp.result()
            else:
                if c.isdigit():
                    if len(operatorbuffer) != 0: # else len(operatorbuffer) == 0 when operator followed by digit
                        self.dsp.process(operatorbuffer)
                        operatorbuffer = ''

                    digitbuffer += c
                else:
                    if len(digitbuffer) != 0: # else len(digitbuffer) == 0 when right parenthesis followed by an operator
                        self.dsp.process(digitbuffer)
                        digitbuffer = ''

                    operatorbuffer += c

        if len(digitbuffer) != 0:
            self.dsp.process(digitbuffer) # else len(digitbuffer) == 0 when expr ends with right parenthesis

        return self.dsp.result()
8.3.2.2.1.3 Refactor the Code

无。

8.3.2.2.2 Test Case 8："2**(1+2)"

前面的"2**3"的测试用例虽然能测试通过，但会导致下面几个测试用例测试失败。

    def test_expr_with_right_parenthesis_followed_by_right_parenthesis(self):
        expr = Expression("(48-(12+34))*10")
        self.assertEquals(20, expr.eval())
        
        expr = Expression("10*(48-(12+34))")
        self.assertEquals(20, expr.eval())

    def test_expr_with_nested_parentheses(self):
        expr = Expression("((10+21)+34)*20")
        self.assertEquals(1300, expr.eval())
        
        expr = Expression("(50-(12+34))*20")
        self.assertEquals(80, expr.eval())
        
        expr = Expression("((11+23)%11)*20")
        self.assertEquals(20, expr.eval())
                
        expr = Expression("(12-(15-12))*10/(24-(12+10))/3")
        self.assertEquals(15, expr.eval())
        
        expr = Expression("(100-(1920-1900))*2/(24-(12+10))/2")
        self.assertEquals(40, expr.eval())

    def test_expr_ends_with_right_parenthesis(self):
        expr = Expression("10*(12+34)")
        self.assertEquals(460, expr.eval())

这几个失败的测试用例的共同点在于，操作符后面紧跟着左括号。借助于"2**(1+2)"测试用例，在eval()中增加操作符后面紧跟着左括号的处理逻辑。

8.3.2.2.2.1 Add a Test
    def test_expr_with_operator_followed_by_left_parenthesis(self):
        expr = Expression("2**(1+2)");
        self.assertEquals(8, expr.eval());
8.3.2.2.2.2 Write the Code

操作符后面紧跟着左括号。

    def eval(self):
        digitbuffer = ''
        operatorbuffer = ''

        while self.ctx.expr_not_end():
            c = self.ctx.next_char()
            if '(' == c:
                if len(operatorbuffer) != 0: # else operatorBuffer.length() == 0 when operator followed by left parenthesis
                    self.dsp.process(operatorbuffer)
                    operatorbuffer = ''

                self.dsp.push_operand(Expression(self.ctx.expr, self.ctx).eval())
            elif ')' == c:
                if len(digitbuffer) != 0: # else len(digitbuffer) == 0 when right parenthesis followed by right parenthesis
                    self.dsp.process(digitbuffer)

                return self.dsp.result()
            else:
                if c.isdigit():
                    if len(operatorbuffer) != 0: # else len(operatorbuffer) == 0 when operator followed by digit
                        self.dsp.process(operatorbuffer)
                        operatorbuffer = ''

                    digitbuffer += c
                else:
                    if len(digitbuffer) != 0: # else len(digitbuffer) == 0 when right parenthesis followed by an operator
                        self.dsp.process(digitbuffer)
                        digitbuffer = ''

                    operatorbuffer += c

        if len(digitbuffer) != 0:
            self.dsp.process(digitbuffer) # else len(digitbuffer) == 0 when expr ends with right parenthesis

        return self.dsp.result()
8.3.2.2.2.3 Refactor the Code

eval()目前的实现存在几个代码的坏味道：代码比较长；操作数的缓存处理、操作符的缓存处理存在重复；代码偏实现、自述性不强等。

  1. 抽取process_operator()方法。

先打算将if('(' == c)分支中的operatorbuffer相关的代码抽取为process_operator()方法。

    def eval(self):
        digitbuffer = ''
        operatorbuffer = ''

        while self.ctx.expr_not_end():
            c = self.ctx.next_char()
            if '(' == c:
                # else operatorBuffer.length() == 0 when operator followed by left parenthesis
                self.process_operator(operatorbuffer)

                self.dsp.push_operand(Expression(self.ctx.expr, self.ctx).eval())
            elif ')' == c:
                if len(digitbuffer) != 0: # else len(digitbuffer) == 0 when right parenthesis followed by right parenthesis
                    self.dsp.process(digitbuffer)

                return self.dsp.result()
            else:
                if c.isdigit():
                    if len(operatorbuffer) != 0: # else len(operatorbuffer) == 0 when operator followed by digit
                        self.dsp.process(operatorbuffer)
                        operatorbuffer = ''

                    digitbuffer += c
                else:
                    if len(digitbuffer) != 0: # else len(digitbuffer) == 0 when right parenthesis followed by an operator
                        self.dsp.process(digitbuffer)
                        digitbuffer = ''

                    operatorbuffer += c

        if len(digitbuffer) != 0:
            self.dsp.process(digitbuffer) # else len(digitbuffer) == 0 when expr ends with right parenthesis

        return self.dsp.result()

    def process_operator(self, operatorbuffer):
        if len(operatorbuffer) != 0:
            self.dsp.process(operatorbuffer)
            operatorbuffer = ''

本以为这样的重构不会有问题，结果却发现下面的测试用例测试不通过了。

    def test_expr_with_nested_parentheses(self):
        expr = Expression("((10+21)+34)*20")
        self.assertEquals(1300, expr.eval())
        
        expr = Expression("(50-(12+34))*20")
        self.assertEquals(80, expr.eval())
        
        expr = Expression("((11+23)%11)*20")
        self.assertEquals(20, expr.eval())
                
        expr = Expression("(12-(15-12))*10/(24-(12+10))/3")
        self.assertEquals(15, expr.eval())
        
        expr = Expression("(100-(1920-1900))*2/(24-(12+10))/2")
        self.assertEquals(40, expr.eval())

分析PyUnit的提示信息，增加打印语句，发现出现了“//”操作符，感觉像是operatorbuffer没有清理干净导致的问题。

仔细查看抽取的process_operator()方法，既然怀疑是operatorbuffer没有清理干净导致的问题，自然会将焦点放在“operatorbuffer = ''”这条语句。这条语句想做的事情是清理以方法参数传入的operatorBuffer，而做事的方式是new了一个新的''字符串对象并赋值给名为operatorbuffer的变量。

    def process_operator(self, operatorbuffer):
        if len(operatorbuffer) != 0:
            self.dsp.process(operatorbuffer)
            operatorbuffer = ''

事实上，问题就出在这里。

因为抽取了process_operator()方法，在方法外面创建的operatorbuffer对象传入方法时，实际是把operatorbuffer对象的引用赋值给了process_operator()方法的形参operatorbuffer变量。需要注意的是，形参的operatorbuffer变量跟传入方法的operatorbuffer对象虽然名字一样，但其实是完全不同的。为了讲述方便，将形参变量重新命名为operatorbuffer'。operatorbuffer和operatorbuffer'两个变量指向了同一个内存地址。如下图所示：

operator buffer 1

“new了一个新的''字符串对象并赋值给名为operatorbuffer的变量”这个操作修改的是operatorbuffer'变量，而operatorbuffer变量并未受到任何影响。如下图所示。所以出现了operatorbuffer没有清理干净的问题。

operator buffer 2

如果不抽取process_operator()方法，不存在方法形参和实参绑定过程中的赋值过程，“new了一个新的''字符串对象并赋值名为operatorbuffer的变量”这个操作修改的就是operatorbuffer变量本身，所以程序运行没有问题。

由于Python的字符串是不可变的，所以将operatorbuffer的类型从字符串改为列表。

    def eval(self):
        digitbuffer = ''
        operatorbuffer = []

        while self.ctx.expr_not_end():
            c = self.ctx.next_char()
            if '(' == c:
                # else operatorBuffer.length() == 0 when operator followed by left parenthesis
                self.process_operator(operatorbuffer)

                self.dsp.push_operand(Expression(self.ctx.expr, self.ctx).eval())
            elif ')' == c:
                if len(digitbuffer) != 0: # else len(digitbuffer) == 0 when right parenthesis followed by right parenthesis
                    self.dsp.process(digitbuffer)

                return self.dsp.result()
            else:
                if c.isdigit():
                    # else len(operatorbuffer) == 0 when operator followed by digit
                    self.process_operator(operatorbuffer)

                    digitbuffer += c
                else:
                    if len(digitbuffer) != 0: # else len(digitbuffer) == 0 when right parenthesis followed by an operator
                        self.dsp.process(digitbuffer)
                        digitbuffer = ''

                    operatorbuffer += c

        if len(digitbuffer) != 0:
            self.dsp.process(digitbuffer) # else len(digitbuffer) == 0 when expr ends with right parenthesis

        return self.dsp.result()

    def process_operator(self, operatorbuffer):
        if len(operatorbuffer) != 0:
            self.dsp.process(self.tostr(operatorbuffer))
            del operatorbuffer[:]

    def tostr(self, lst):
        return ''.join(lst)

operatorbuffer和operatorbuffer'对象的引用情况，如下图所示：

operator buffer 1

del操作修改的是两个对象引用共同指向的内存。operatorbuffer就能被清理干净了。

operator buffer 3

事实上，这么修改之后，之前测试不通过的测试用例就测试通过了。

  1. 抽取process_operand()方法。需注意：
  • 将digitbuffer的类型从字符串改为列表。
  • 重构前的代码中，有些digitbuffer相关的代码是不需要del操作的，这里为了可以抽取统一的方法，统一加上了del操作，不影响逻辑。
    def eval(self):
        digitbuffer = []
        operatorbuffer = []

        while self.ctx.expr_not_end():
            c = self.ctx.next_char()
            if '(' == c:
                # else operatorBuffer.length() == 0 when operator followed by left parenthesis
                self.process_operator(operatorbuffer)

                self.dsp.push_operand(Expression(self.ctx.expr, self.ctx).eval())
            elif ')' == c:
                # else len(digitbuffer) == 0 when right parenthesis followed by right parenthesis
                self.process_operand(digitbuffer)

                return self.dsp.result()
            else:
                if c.isdigit():
                    # else len(operatorbuffer) == 0 when operator followed by digit
                    self.process_operator(operatorbuffer)

                    digitbuffer += c
                else:
                    # else len(digitbuffer) == 0 when right parenthesis followed by an operator
                    self.process_operand(digitbuffer)

                    operatorbuffer += c

        # else len(digitbuffer) == 0 when expr ends with right parenthesis
        self.process_operand(digitbuffer)
        
        return self.dsp.result()

    def process_operand(self, digitbuffer):
        if len(digitbuffer) != 0:
            self.dsp.process(self.tostr(digitbuffer))
            del digitbuffer[:]
  1. process_operator和process_operand()方法有重复，重构去重。
    def process_operator(self, operatorbuffer):
        self.process_operelement(operatorbuffer)

    def process_operand(self, digitbuffer):
        self.process_operelement(digitbuffer)

    def process_operelement(self, buffer):
        if len(buffer) != 0:
            self.dsp.process(self.tostr(buffer))
            del buffer[:]

8.4 negative integer

表达式支持负整数。

代码路径：oo.negint

由Expression完成负数的解析。负号的判断方法是，首先它是一个“-”，其次，“-”是表达式的开头或者“-”前面是左括号。
isdigit()对于包含正负号的数字字符串无效，增加isint()方法。

先后分别修改DoubleStackProcessor和Expression的测试代码和产品代码。

8.4.1 DoubleStackProcessor

操作数支持负号。

8.4.1.1 Test Cases

测试用例如下：

19. -10  (操作数支持负号)

8.4.1.2 Coding

8.4.1.2.1 Test Case 19：-10

操作数支持负号。

8.4.1.2.1.1 Add a Test
    def test_negative_num(self):
        dsp.process('-10');
        
        self.assertEquals([-10], self.dsp._dump_operandstack())
        self.assertEquals([], self.dsp._dump_operatorstack())
8.4.1.2.1.2 Write the Code
import re

    def process(self, item):
        if isint(item):
            self.process_operand(item)
        else:
            self.process_operator(item)

    def isint(self, item):
        return re.match(r'-?\b[0-9]+\b', item)
8.4.1.2.1.3 Refactor the Code

无。

8.4.2 Expression

完成负数的解析。负号的判断方法是，首先它是一个“-”，其次，“-”是表达式的开头或者“-”前面是左括号。

8.4.2.1 Test Cases

测试用例如下：

9.  "-12"   (eval()中增加表达式以负号开头的处理逻辑)
10. "(-12)" (eval()中增加负号前面是左括号的处理逻辑)

8.4.2.2 Coding

8.4.2.2.1 Test Case 9："-12"

eval()中增加表达式以负号开头的处理逻辑。

8.4.2.2.1.1 Add a Test
    def test_expr_with_minus_when_expr_starts_with_minus(self):
        expr = Expression("-12")
        assertEquals(-12, expr.eval())
8.4.2.2.1.2 Write the Code

Expression Class

    def eval(self):
        digitbuffer = []
        operatorbuffer = []

        while self.ctx.expr_not_end():
            c = self.ctx.next_char()
            if '(' == c:
                # else operatorBuffer.length() == 0 when operator followed by left parenthesis
                self.process_operator(operatorbuffer)

                self.dsp.push_operand(Expression(self.ctx.expr, self.ctx).eval())
            elif ')' == c:
                # else len(digitbuffer) == 0 when right parenthesis followed by right parenthesis
                self.process_operand(digitbuffer)

                return self.dsp.result()
            else:
                if c.isdigit():
                    # else len(operatorbuffer) == 0 when operator followed by digit
                    self.process_operator(operatorbuffer)

                    digitbuffer += c
                elif self.minus_leading_expr(c):
                    digitbuffer.append(c)
                else:
                    # else len(digitbuffer) == 0 when right parenthesis followed by an operator
                    self.process_operand(digitbuffer)

                    operatorbuffer += c

        # else len(digitbuffer) == 0 when expr ends with right parenthesis
        self.process_operand(digitbuffer)
        
        return self.dsp.result()

    def minus_leading_expr(self, c):
        return c == '-' and self.ctx.curchar_leading_expr()

Context Class

    def curchar_leading_expr(self):
        return self.curidx == 1
8.4.2.2.1.3 Refactor the Code

无。

8.4.2.2.2 Test Case 10："(-12)"

eval()中增加负号前面是左括号的处理逻辑。

8.4.2.2.2.1 Add a Test
    def test_expr_with_minus_when_negative_num_wrapped_with_parentheses(self):
        expr = Expression("(-12)")
        self.assertEquals(-12, expr.eval())
8.4.2.2.2.2 Write the Code

Expression Class

    def minus_leading_expr(self, c):
        return c == '-' and (self.ctx.curchar_leading_expr() or '(' == self.ctx.prev_char())

Context Class

    def prev_char(self):
        return self.expr[self.curidx - 2]
8.4.2.2.2.3 Refactor the Code

无。

8.4.2.3 Final Test Cases

至此支持负整数的代码已全部实现。这里只是用一些复杂的测试用例验证一下。

    def test_expr_with_minus(self):
        expr = Expression("((12))")
        self.assertEquals(12, expr.eval())
        
        expr = Expression("-10+20")
        self.assertEquals(10, expr.eval())
        
        expr = Expression("(-10)+20")
        self.assertEquals(10, expr.eval())
        
        expr = Expression("20+(-10)")
        self.assertEquals(10, expr.eval())
        
        expr = Expression("(-11+12)*1-15+12/2")
        self.assertEquals(-8, expr.eval())
        
        expr = Expression("(11+12)*(-1)-(15+12/2)")
        self.assertEquals(-44, expr.eval())
        
        expr = Expression("((12+(-11))*2-11)*3")
        self.assertEquals(-27, expr.eval())

8.5 Parser

在支持了多位正整数、幂操作符和负整数以后，Expression类的eval()方法变得有些难以理解，表达式解析逻辑和递归逻辑混在了一起。

新定义一个Parser类专门负责表达式解析。把Expression类的eval()方法中的解析逻辑挪到Parser类中。Context类的解析逻辑，如expr_not_end ()、next_char()等方法，也挪到Parser类中。

Context类变成一个纯数据类。Parser类负责解析。Expression类包含Context、DoubleStackProcessor和Parser成员变量，它的eval()方法中主要是递归逻辑。也就是说每一个表达式/子表达式都拥有自己的DoubleStackProcessor和Parser。

代码路径：oo.parser

8.5.1 Test Cases

在DoubleStackProcessor类已经支持多位正整数、多位操作符和负整数的前提下，重写Expression类。

测试用例如下：

1. "12"                   (驱动出Expression/Parser/Context主体代码和处理多位数的逻辑)
2. "10**2"                (驱动出处理多位操作符的逻辑)
3. "-12"                  (驱动出处理负号的逻辑)
4. "10*(48-(12+34))"      (驱动出处理括号但不含负号的逻辑，主要是递归逻辑)
5. "((12+(-11))*2-11)**2" (驱动出处理括号且含负号的逻辑)

8.5.2 Coding

8.5.2.1 Test Case 1: "12"

驱动出Expression/Parser/Context主体代码和处理多位数的逻辑。

8.5.2.1.1 Add a Test

test_expression.py

import unittest

from expression import Expression

class TestExpression(unittest.TestCase):
    def test_multidigit_operand(self):
        expr = Expression("12")
        self.assertEquals(12, expr.eval())
8.5.2.1.2 Write the Code

expression.py Expression Class

from doublestackprocessor import DoubleStackProcessor

class Expression(object):
    def __init__(self, expr, context=None):
        if context == None:
            self.ctx = Context(expr, 0)
        else:
            self.ctx = context

        self.dsp = DoubleStackProcessor()
        self.parser = Parser(self.ctx)

    def eval(self):
        while self.parser.expr_not_end():
            item = self.parser.next_item()
            self.dsp.process(item)
        
        return self.dsp.result()

expression.py Parser Class

class Parser(object):
    def __init__(self, ctx):
        self.ctx = ctx

    def expr_not_end(self):
        return self.ctx.curidx < len(self.ctx.expr)

    def next_item(self):
        c = self._next_char()
        return c + self._subsequence(c)

    def _next_char(self):
        c = self.ctx.expr[self.ctx.curidx]
        self.ctx.curidx += 1
        return c

    def _subsequence(self, c):
        return self._next_operand()

    def _next_operand(self):
        result = ''
        while self._peek_char().isdigit():
            result += self._next_char()
        return result

    def _peek_char(self):
        return self.ctx.expr[self.ctx.curidx] if self.expr_not_end() else ''

expression.py Context Class

class Context(object):
    def __init__(self, expr, curidx):
        self.expr = expr
        self.curidx = curidx
8.5.2.1.3 Refactor the Code

无。

8.5.2.2 Test Case 2: "10**2"

驱动出处理多位操作符的逻辑。

8.5.2.2.1 Add a Test

test_expression.py

    def test_multichar_operator(self):
        expr = Expression("10**2")
        self.assertEquals(100, expr.eval())
8.5.2.2.2 Write the Code

expression.py Parser Class

    def _subsequence(self, c):
        if c.isdigit():
            return self._next_operand()

        if self._isopchar(c):
            return self._next_operator()

    def _next_operator(self):
        result = ''
        while self._isopchar(self._peek_char()):
            result += self._next_char()
        return result

    def _isopchar(self, c):
        return c in '+-*/%'
8.5.2.2.3 Refactor the Code

无。

8.5.2.3 Test Case 3: "-12"

驱动出处理负号的逻辑。

8.5.2.3.1 Add a Test

test_expression.py

    def test_negative_operand(self):
        expr = Expression("-12")
        self.assertEquals(-12, expr.eval())
8.5.2.3.2 Write the Code

expression.py Parser Class

    def _subsequence(self, c):
        if c.isdigit():
            return self._next_operand()

        if self._isnegative(c):
            return self._next_operand()

        if self._isopchar(c):
            return self._next_operator()

    def _isnegative(self, c):
        return c == '-' and self.ctx.curidx == 1
  • 减号在表达式开头是负号。
  • 在_subsequence()方法中，_isnegative(c)判断分支要放在_isopchar(c)判断分支之前，否则会被先判断为减号操作符。
8.5.2.3.3 Refactor the Code

1 Parser类中的_next_operand()方法和_next_operator()方法存在重复代码，抽取_next_item(pred)方法。

expression.py Parser Class

    def _next_operand(self):
        return self._next_item(self._isdigitchar)

    def _next_operator(self):
        return self._next_item(self._isopchar)

    def _next_item(self, pred):
        result = ''
        while pred(self._peek_char()):
            result += self._next_char()
        return result

    def _isdigitchar(self, c):
        return c.isdigit()

2 优化_subsequence()方法的分支逻辑。

expression.py Parser Class

    def _subsequence(self, c):
        if c.isdigit() or self._isnegative(c):
            return self._next_operand()

        if self._isopchar(c):
            return self._next_operator()

8.5.2.4 Test Case 4: "10*(48-(12+34))"

驱动出处理括号但不含负号的逻辑，主要是递归逻辑。

8.5.2.4.1 Add a Test

test_expression.py

    def test_parenthesis_without_negative(self):
        expr = Expression("10*(48-(12+34))")
        self.assertEquals(20, expr.eval())
8.5.2.4.2 Write the Code

expression.py Expression Class

    def eval(self):
        while self.parser.expr_not_end():
            item = self.parser.next_item()
            if '(' == item:
                self.dsp.push_operand(Expression(self.ctx.expr, self.ctx).eval())
            elif ')' == item:
                return self.dsp.result()
            else:
                self.dsp.process(item)
        
        return self.dsp.result()

expression.py Parser Class

    def _subsequence(self, c):
        if c.isdigit() or self._isnegative(c):
            return self._next_operand()

        if self._isopchar(c):
            return self._next_operator()

        return ''

因为要支持括号，expr_not_end()方法不能用来判断子表达式是否结束，Parser类的_subsequence()方法需要加上返回''的分支，否则Python缺省返回None。

8.5.2.4.3 Refactor the Code

无。

8.5.2.5 Test Case 5: "((12+(-11))*2-11)**2"

驱动出处理括号且含负号的逻辑。

8.5.2.5.1 Add a Test

test_expression.py

    def test_parenthesis_with_negative(self):
        expr = Expression("((12+(-11))*2-11)**2")
        self.assertEquals(81, expr.eval())
8.5.2.5.2 Write the Code

expression.py Parser Class

    def _prev_char(self):
        return self.ctx.expr[self.ctx.curidx - 2]

    def _isnegative(self, c):
        return c == '-' and (self.ctx.curidx == 1 or self._prev_char() == '(')

_isnegative()方法增加减号前面是“(”的判断分支，这种情况下减号是负号。

8.5.2.5.3 Refactor the Code

无。

9. OO vs. Process

前面都是用面向对象(Object-Oriented, OO)的方式实现的，也可以用面向过程(Process-Oriented, PO)的方式实现。在PO实现方式中，因为无法保存状态，操作数栈和操作符栈都需要以函数参数的形式从头传到尾。

以OO方式实现的代码都在oo目录下，以PO方式实现的代码都在po目录下。

用PO的方式实现了最基本的单位正整数的加、减、乘、除运算。

代码路径：po.original

test_all.py

import unittest

from tests.test_doublestackprocessor import TestDoubleStackProcessor
from tests.test_expression import TestExpression

if __name__ == '__main__':
    unittest.main()

tests.test_doublestackprocessor.py

import unittest

import doublestackprocessor as dsp

class TestDoubleStackProcessor(unittest.TestCase):
    def setUp(self):
        self.operandstack = []
        self.operatorstack = []

    def test_num(self):
        dsp.process('3', self.operandstack, self.operatorstack)

        self.assertEquals([3], dsp._dump(self.operandstack))

    def test_num_plus(self):
        dsp.process('3', self.operandstack, self.operatorstack)
        dsp.process('+', self.operandstack, self.operatorstack)

        self.assertEquals([3], dsp._dump(self.operandstack))
        self.assertEquals(['+'], dsp._dump(self.operatorstack))

    def test_num_plus_num_plus(self):
        dsp.process('3', self.operandstack, self.operatorstack)
        dsp.process('+', self.operandstack, self.operatorstack)
        dsp.process('2', self.operandstack, self.operatorstack)
        dsp.process('+', self.operandstack, self.operatorstack)

        self.assertEquals([5], dsp._dump(self.operandstack))
        self.assertEquals(['+'], dsp._dump(self.operatorstack))

    def test_num_multiply_num_multiply(self):
        dsp.process('3', self.operandstack, self.operatorstack)
        dsp.process('*', self.operandstack, self.operatorstack)
        dsp.process('2', self.operandstack, self.operatorstack)
        dsp.process('*', self.operandstack, self.operatorstack)

        self.assertEquals([6], dsp._dump(self.operandstack))
        self.assertEquals(['*'], dsp._dump(self.operatorstack))

    def test_num_multiply_num_plus(self):
        dsp.process('3', self.operandstack, self.operatorstack)
        dsp.process('*', self.operandstack, self.operatorstack)
        dsp.process('2', self.operandstack, self.operatorstack)
        dsp.process('+', self.operandstack, self.operatorstack)

        self.assertEquals([6], dsp._dump(self.operandstack))
        self.assertEquals(['+'], dsp._dump(self.operatorstack))

    def test_num_plus_num_multiply_num_plus(self):
        dsp.process('3', self.operandstack, self.operatorstack)
        dsp.process('+', self.operandstack, self.operatorstack)
        dsp.process('2', self.operandstack, self.operatorstack)
        dsp.process('*', self.operandstack, self.operatorstack)
        dsp.process('3', self.operandstack, self.operatorstack)
        dsp.process('+', self.operandstack, self.operatorstack)

        self.assertEquals([9], dsp._dump(self.operandstack))
        self.assertEquals(['+'], dsp._dump(self.operatorstack))

    def test_num_plus_num_subtract(self):
        dsp.process('3', self.operandstack, self.operatorstack)
        dsp.process('+', self.operandstack, self.operatorstack)
        dsp.process('2', self.operandstack, self.operatorstack)
        dsp.process('-', self.operandstack, self.operatorstack)

        self.assertEquals([5], dsp._dump(self.operandstack))
        self.assertEquals(['-'], dsp._dump(self.operatorstack))

    def test_num_subtract_num_plus(self):
        dsp.process('3', self.operandstack, self.operatorstack)
        dsp.process('-', self.operandstack, self.operatorstack)
        dsp.process('2', self.operandstack, self.operatorstack)
        dsp.process('+', self.operandstack, self.operatorstack)

        self.assertEquals([1], dsp._dump(self.operandstack))
        self.assertEquals(['+'], dsp._dump(self.operatorstack))

    def test_num_subtract_num_divide(self):
        dsp.process('4', self.operandstack, self.operatorstack)
        dsp.process('-', self.operandstack, self.operatorstack)
        dsp.process('2', self.operandstack, self.operatorstack)
        dsp.process('/', self.operandstack, self.operatorstack)

        self.assertEquals([4, 2], dsp._dump(self.operandstack))
        self.assertEquals(['-', '/'], dsp._dump(self.operatorstack))

    def test_num_divide_num_plus(self):
        dsp.process('4', self.operandstack, self.operatorstack)
        dsp.process('/', self.operandstack, self.operatorstack)
        dsp.process('2', self.operandstack, self.operatorstack)
        dsp.process('+', self.operandstack, self.operatorstack)

        self.assertEquals([2], dsp._dump(self.operandstack))
        self.assertEquals(['+'], dsp._dump(self.operatorstack))

    def test_result_num(self):
        dsp.process('3', self.operandstack, self.operatorstack)

        self.assertEquals(3, dsp.result(self.operandstack, self.operatorstack))
        self.assertEquals([], dsp._dump(self.operandstack))
        self.assertEquals([], dsp._dump(self.operatorstack))

    def test_result_calc_once(self):
        dsp.process('1', self.operandstack, self.operatorstack)
        dsp.process('+', self.operandstack, self.operatorstack)
        dsp.process('2', self.operandstack, self.operatorstack)

        self.assertEquals(3, dsp.result(self.operandstack, self.operatorstack))
        self.assertEquals([], dsp._dump(self.operandstack))
        self.assertEquals([], dsp._dump(self.operatorstack))

    def test_result_calc_twice(self):
        dsp.process('1', self.operandstack, self.operatorstack)
        dsp.process('+', self.operandstack, self.operatorstack)
        dsp.process('2', self.operandstack, self.operatorstack)
        dsp.process('*', self.operandstack, self.operatorstack)
        dsp.process('3', self.operandstack, self.operatorstack)

        self.assertEquals(7, dsp.result(self.operandstack, self.operatorstack))
        self.assertEquals([], dsp._dump(self.operandstack))
        self.assertEquals([], dsp._dump(self.operatorstack))

doublestackprocessor.py

import copy

operator_func_map = {'+':lambda x, y: x + y,
                     '-':lambda x, y: x - y,
                     '*':lambda x, y: x * y,
                     '/':lambda x, y: x / y}

operator_priority_map = {'+':1, '-':1, '*':2, '/':2}

def process(c, operandstack, operatorstack):
    if c.isdigit():
        process_operand(c, operandstack)
    else:
        process_operator(c, operandstack, operatorstack)

def result(operandstack, operatorstack):
    calc(operandstack, operatorstack)
    return pop_operand(operandstack)

def calc(operandstack, operatorstack):
    while not_empty(operatorstack):
        calc_once(operandstack, operatorstack)

def process_operand(c, operandstack):
    push_operand(int(c), operandstack)

def process_operator(c, operandstack, operatorstack):
    while not_empty(operatorstack) and not_prior_to(c, top_operator(operatorstack)):
        calc_once(operandstack, operatorstack)

    push_operator(c, operatorstack)

def not_empty(operatorstack):
    return len(operatorstack) != 0

def not_prior_to(operator1, operator2):
    return priority(operator1) <= priority(operator2)

def priority(operator):
    return operator_priority_map[operator]

def calc_once(operandstack, operatorstack):
    r_operand = pop_operand(operandstack)
    l_operand = pop_operand(operandstack)
    operator = pop_operator(operatorstack)
    push_operand(apply(operator, l_operand, r_operand), operandstack)

def apply(operator, l_operand, r_operand):
    return operator_func_map[operator](l_operand, r_operand)

def push_operand(operand, operandstack):
    operandstack.append(operand)

def pop_operand(operandstack):
    return operandstack.pop()

def push_operator(operator, operatorstack):
    operatorstack.append(operator)

def pop_operator(operatorstack):
    return operatorstack.pop()

def top_operator(operatorstack):
    return operatorstack[-1]

def _dump(stack):
    return copy.copy(stack)

tests.test_expression.py

import unittest

import expression as expr

class TestExpression(unittest.TestCase):
    def test_num(self):
        self.assertEquals(3, expr.eval_expr("3"))

    def test_expr_has_parentheses(self):
        self.assertEquals(6, expr.eval_expr("2*(1+2)"))

    def test_expr_final(self):
        self.assertEquals(8, expr.eval_expr("((1+2)+1)*2"))
        self.assertEquals(8, expr.eval_expr("(1+(1+2))*2"))
        self.assertEquals(6, expr.eval_expr("(2-(1-2))*3+(2-(2+1))*3"))

expression.py

import doublestackprocessor as dsp

def eval_expr(expr):
    return _eval_expr(expr, [0], [], [])

def _eval_expr(expr, wcuridx, operandstack, operatorstack):
    while expr_not_end(expr, wcuridx):
        c = next_char(expr, wcuridx)
        if '(' == c:
            dsp.push_operand(_eval_expr(expr, wcuridx, [], []), operandstack)
        elif ')' == c:
            return dsp.result(operandstack, operatorstack)
        else:
            dsp.process(c, operandstack, operatorstack)

    return dsp.result(operandstack, operatorstack)

def expr_not_end(expr, wcuridx):
    return wcuridx[0] < len(expr)

def next_char(expr, wcuridx):
    c = expr[wcuridx[0]]
    wcuridx[0] += 1
    return c
⚠️ **GitHub.com Fallback** ⚠️