201710 TDD Coding Practice Arithmetic (Double Stack Algorithm) - xiaoxianfaye/Courses GitHub Wiki
- 1 Problem
- 2 Showcase & Discuss
- 3 Analysis
- 4 Design
-
5 Implementation
- 5.1 Instructions
-
5.2 DoubleStackProcessor
- 5.2.1 Test Cases
-
5.2.2 Coding
- 5.2.2.1 Test Case 1：3
- 5.2.2.2 Test Case 2：3+
- 5.2.2.3 Test Case 3：3+2+
- 5.2.2.4 Test Case 4：3+2*
- 5.2.2.5 Test Case 5：3*2*
- 5.2.2.6 Test Case 6：3*2+
- 5.2.2.7 Test Case 7：3+2*3+
- 5.2.2.8 Test Case 8：3+2-
- 5.2.2.9 Test Case 9：3-2+
- 5.2.2.10 Test Case 10：4-2/
- 5.2.2.11 Test Case 11：4/2+
- 5.2.2.12 Test Case 12："3"
- 5.2.2.13 Test Case 13："1+2"
- 5.2.2.14 Test Case 14："1+2*3"
- 5.3 Expression
- 5.4 Test Suite
- 6 Summary
- 7 Homework
-
8 My Homework
- 8.1 Rem
-
8.2 Multi-digit Positive Integer
- 8.2.1 DoubleStackProcessor
-
8.2.2 Expression
- 8.2.2.1 Test Cases
-
8.2.2.2 Coding
- 8.2.2.2.1 Test Case 1："12"
- 8.2.2.2.2 Test Case 2："12+34"
- 8.2.2.2.3 Test Case 3："12+34*10"
- 8.2.2.2.4 Test Case 4："(12+34)*10"
- 8.2.2.2.5 Test Case 5："10*(12+34)"
- 8.2.2.2.6 Test Case 6："(48-(12+34))*10"、"10*(48-(12+34))"
- 8.2.2.2.7 Final Test Cases
- 8.2.2.2.8 Delete All Useless TestCases and Product Code
-
8.3 Pow **
-
8.3.1 Change the Element Type of Operator Stack
- 8.3.1.1 DoubleStackProcessor
-
8.3.1.2 Expression
- 8.3.1.2.1 Test Cases
-
8.3.1.2.2 Coding
- 8.3.1.2.2.1 Test Case 1："12"
- 8.3.1.2.2.2 Test Case 2："12+34"
- 8.3.1.2.2.3 Test Case 3："12+34*10"
- 8.3.1.2.2.4 Test Case 4："(12+34)*10"
- 8.3.1.2.2.5 Test Case 5："10*(12+34)"
- 8.3.1.2.2.6 Test Case 6："(48-(12+34))*10"、"10*(48-(12+34))"
- 8.3.1.2.2.7 Final Test Cases
- 8.3.1.2.2.8 Delete All Useless TestCases and Product Code
- 8.3.2 Pow **
-
8.3.1 Change the Element Type of Operator Stack
- 8.4 negative integer
- 8.5 Parser
编写一个简单的计算器，该计算器目前只需要支持单位正整数的加、减、乘、除运算，并支持用括号表示优先级别。和我们小学时学过的算术规则一致，乘法和除法的优先级一样，加法和减法的优先级一样。乘除法的优先级高于加减法。括号的优先级最高。同一优先级的运算顺序为自左向右。几个简单的例子如下：
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，输入字符串类型的表达式，输出整数类型的运算结果。
请学员展示自己之前的设计思路和实现方式，大家可以互相点评、讨论。以学员为主，讲师为辅。
分析：定义清楚问题是什么。
- 表达式：Expression
- 操作数：Operand
- 操作符：Operator
- 子表达式：SubExpression
- 进入系统的表达式是规格化后合法的表达式。
- 表达式的规格化和合法性校验放在系统边界以外。
- 操作数均为单位正整数。
- 操作符只包括：+ - * /，其中除法均为整除。
- 子表达式用圆括号()括起来，可嵌套。
6 * (( 1+ 3) / 2) --规格化--> 6*((1+3)/2)
Illegal Expressions (可以让学员讲一下怎么不合法)：
(-16)**2 多位正整数、非法操作符
2++3 非法操作符
(1+2)-3) 括号不对称
- 操作符优先级：+ 和 - 同级， * 和 / 同级， * 和 / 优先级高于 + 和 -。
- 优先级相同的情况下，“+ - * /”操作符都是左结合 (自左向右进行运算)。
- 先看优先级、再看结合性。
- ()优先级最高。
用以下几个表达式讲解双栈算法，可以让学员来讲。
1+2
3+2-1
1+2*3
1+2*3-1
- 当前字符为操作数时，直接压栈；
- 当前字符为操作符时，如果操作符栈为空或当前操作符的优先级高于栈顶操作符时，压栈；如果当前操作符的优先级低于或等于栈顶操作符时，从操作数栈弹出两个操作数(注意顺序)，从操作符栈弹出一个操作符，进行运算，并将运算结果压入操作数栈；
- 当到达表达式末尾时，依次弹出两个操作数和一个操作符进行运算，并将运算结果压入操作数栈，如此反复，直到操作符栈为空，此时操作数栈应该只有一个最终的运算结果。
Quiz (向学员提问，看看是否真的理解了双栈算法)
Q：操作数栈和操作符栈的大小是否有最大值？如果有，分别是多少？
A：操作数栈的最大长度是3，操作符栈的最大长度是2。
设计：问题分析清楚以后，提出解决问题的逻辑框架。
- 输入：表达式“字符串”、输出：“整型”结果。
- 分层：
- Expression：将表达式字符串解析成单个字符。
- DoubleStackProcessor：接收Expression解析出的单个字符进行双栈算法的处理。
- TDD三步军规、小步。
- 测试：
- 始终选择当前最有价值的测试用例；
- 测试三段式：Arrange、Act、Assert；
- 不要忘了测试代码也需要重构；
- 合理使用TestSuite。
- 规范：
- 代码目录规范：testsrc、src；
- 类名命名规范：XyzTest、Xyz。
- 每次修改代码，都运行一下测试用例，注意红绿绿的节奏。
- 写代码应做到：
- 简洁明了：概念定义清晰、准确；简明清晰地表达语义；
- 表达到位：层次分明、表现意图；跟问题领域的概念、规则相吻合；
- 安全可靠：状态、时序管理得当；具有必要的测试安全网络。
- 开始写一个测试用例前，先让学员思考如何写测试、如何验证。
1. 3 (驱动出Operand Stack相关代码)
2. 3+ (驱动出Operator Stack相关代码)
3. 3+2+ (驱动出calcOnce和加法计算)
4. 3+2* (驱动出当前操作符“+”和栈顶操作符“*”的条件判断)
5. 3*2* (驱动出apply和乘法计算)
6. 3*2+ (测试用例直接测试通过，按照双栈算法描述重构代码)
7. 3+2*3+ (驱动出while{calcOnce})
8. 3+2- (驱动出“-”的优先级映射)
9. 3-2+ (驱动出“-”的计算函数映射)
10. 4-2/ (驱动出“/”的优先级映射)
11. 4/2+ (驱动出“/”的计算函数映射)
12. "3" (驱动出result popOperand)
13. "1+2" (驱动出result if{calcOnce})
14. "1+2*3" (驱动出result while{calcOnce})
驱动出Operand Stack相关代码。
新增一个测试用例。要注意：
- 测试方法名要有含义，能体现测试场景；
- Wishful Thinking。此时编译不通过是正常的，不要着急让代码编译通过。
public class DoubleStackProcessorTest extends TestCase
{
public void test_num()
{
DoubleStackProcessor dsp = new DoubleStackProcessor();
dsp.process('3');
assertEquals(1, dsp.getOperandStackSize());
assertEquals(3, dsp.getOperandFromStack(0));
}
}添加恰好足够的代码使所有(含新增)测试用例快速通过。要注意：
- 分两个步骤：补齐代码编译通过，再让测试通过；
- 补齐代码时，注意IDE自动生成的代码有时不一定是我们想要的，一定要仔细看，修改成我们想要的；
- 用最直白的方式让代码尽快通过测试；
- 测试失败时，注意仔细查看JUnit的提示，根据提示分析解决问题，不要着急。
- getOperandStackSize()和getOperandFromStack()只供测试代码调用，因此访问属性是包可访问，而不是public。
- 产品代码中包含一点点测试辅助代码是可以。在这里，如果不增加getOperandStackSize()和getOperandFromStack()方法，就要以别的方式把Operand Stack的数据结构暴露出去，更不好。关于测试辅助代码需要注意几点：
- 测试辅助代码的逻辑要非常简单，且不能包含业务逻辑。
- 严格控制测试辅助方法的访问属性。
- 测试辅助代码尽量少。
public class DoubleStackProcessor
{
private static final int OPERAND_STACK_MAX_SIZE = 3;
private int[] operands = new int[OPERAND_STACK_MAX_SIZE];
private int idxOfOperands = 0;
public void process(char c)
{
operands[idxOfOperands++] = c - '0';
}
int getOperandStackSize()
{
return idxOfOperands;
}
int getOperandFromStack(int idx)
{
return operands[idx];
}
}- 抽取toInt()方法。
public void process(char c)
{
operands[idxOfOperands++] = toInt(c);
}
private int toInt(char c)
{
return c - '0';
}- 抽取pushOperands()方法。
首先，将toInt(c)提取为局部变量operand。
public void process(char c)
{
int operand = toInt(c);
operands[idxOfOperands++] = operand;
}然后，再提取pushOperand()方法。
public void process(char c)
{
int operand = toInt(c);
pushOperand(operand);
}
private void pushOperand(int operand)
{
operands[idxOfOperands++] = operand;
}最后，将局部变量operand内联入pushOperand()方法。
public void process(char c)
{
pushOperand(toInt(c));
}驱动出Operator Stack相关代码。
public void test_num_plus()
{
DoubleStackProcessor dsp = new DoubleStackProcessor();
dsp.process('3');
dsp.process('+');
assertEquals(1, dsp.getOperandStackSize());
assertEquals(3, dsp.getOperandFromStack(0));
assertEquals(1, dsp.getOperatorStackSize());
assertEquals('+', dsp.getOperatorFromStack(0));
}getOperatorStackSize()和getOperatorFromStack()方法只供测试代码调用，因此访问属性是包可访问，而不是public。
private static final int OPERATOR_STACK_MAX_SIZE = 2;
private char[] operators = new char[OPERATOR_STACK_MAX_SIZE];
private int idxOfOperators = 0;
public void process(char c)
{
if('0' <= c && c <= '9')
{
pushOperand(toInt(c));
}
else
{
operators[idxOfOperators++] = c;
}
}
int getOperatorStackSize()
{
return idxOfOperators;
}
char getOperatorFromStack(int idx)
{
return operators[idx];
}重构产品代码。
- 抽取isDigit()方法。
public void process(char c)
{
if(isDigit(c))
{
pushOperand(toInt(c));
}
else
{
operators[idxOfOperators++] = c;
}
}
private boolean isDigit(char c)
{
return '0' <= c && c <= '9';
}- 抽取pushOperator()方法。
public void process(char c)
{
if(isDigit(c))
{
pushOperand(toInt(c));
}
else
{
pushOperator(c);
}
}
private void pushOperator(char operator)
{
operators[idxOfOperators++] = operator;
}重构测试代码。
- 将dsp提升为成员变量，增加setUp()方法，在setUp()方法中初始化dsp。
private DoubleStackProcessor dsp;
@Override
protected void setUp()
{
dsp = new DoubleStackProcessor();
}
public void test_num()
{
dsp.process('3');
assertEquals(1, dsp.getOperandStackSize());
assertEquals(3, dsp.getOperandFromStack(0));
}
public void test_num_plus()
{
dsp.process('3');
dsp.process('+');
assertEquals(1, dsp.getOperandStackSize());
assertEquals(3, dsp.getOperandFromStack(0));
assertEquals(1, dsp.getOperatorStackSize());
assertEquals('+', dsp.getOperatorFromStack(0));
}- 改进Stack的assert。
import static java.util.Arrays.asList;
public void test_num()
{
dsp.process('3');
assertEquals(asList(3), dsp.dumpOperandStack());
assertEquals(asList(), dsp.dumpOperatorStack());
}
public void test_num_plus()
{
dsp.process('3');
dsp.process('+');
assertEquals(asList(3), dsp.dumpOperandStack());
assertEquals(asList('+'), dsp.dumpOperatorStack());
}产品代码增加dumpOperandStack()和dumpOperatorStack()方法，删除getOperandStackLength()、getOperandFromStack()、getOperatorStackLength()和getOperatorFromStack()方法。
import java.util.ArrayList;
import java.util.List;
List<Integer> dumpOperandStack()
{
List<Integer> dumped = new ArrayList<>();
for(int i = 0; i < idxOfOperands; i++)
{
dumped.add(operands[i]);
}
return dumped;
}
List<Character> dumpOperatorStack()
{
List<Character> dumped = new ArrayList<>();
for(int i = 0; i < idxOfOperators; i++)
{
dumped.add(operators[i]);
}
return dumped;
}dumpOperandStack()和dumpOperatorStack()之间有重复代码，可以引入Java8的新特性——流，减少重复代码。
import java.util.stream.IntStream;
import static java.util.stream.Collectors.toList;
List<Integer> dumpOperandStack()
{
return IntStream.range(0, idxOfOperands).mapToObj(i -> operands[i]).collect(toList());
}
List<Character> dumpOperatorStack()
{
return IntStream.range(0, idxOfOperators).mapToObj(i -> operators[i]).collect(toList());
}驱动出calcOnce和加法计算。
public void test_num_plus_num_plus()
{
dsp.process('3');
dsp.process('+');
dsp.process('2');
dsp.process('+');
assertEquals(asList(5), dsp.dumpOperandStack());
assertEquals(asList('+'), dsp.dumpOperatorStack());
} public void process(char c)
{
if(isDigit(c))
{
pushOperand(toInt(c));
}
else
{
if(idxOfOperators != 0)
{
int rOperand = operands[--idxOfOperands];
int lOperand = operands[--idxOfOperands];
char operator = operators[--idxOfOperators];
pushOperand(lOperand + rOperand);
}
pushOperator(c);
}
}- 抽取notEmptyOperatorStack()方法。
public void process(char c)
{
if(isDigit(c))
{
pushOperand(toInt(c));
}
else
{
if(notEmptyOperatorStack())
{
int rOperand = operands[--idxOfOperands];
int lOperand = operands[--idxOfOperands];
char operator = operators[--idxOfOperators];
pushOperand(lOperand + rOperand);
}
pushOperator(c);
}
}
private boolean notEmptyOperatorStack()
{
return idxOfOperators != 0;
}- 抽取calcOnce()方法。
public void process(char c)
{
if(isDigit(c))
{
pushOperand(toInt(c));
}
else
{
if(notEmptyOperatorStack())
{
calcOnce();
}
pushOperator(c);
}
}
private void calcOnce()
{
int rOperand = operands[--idxOfOperands];
int lOperand = operands[--idxOfOperands];
char operator = operators[--idxOfOperators];
pushOperand(lOperand + rOperand);
}- 抽取popOperand()和popOperator()方法。
private void calcOnce()
{
int rOperand = popOperand();
int lOperand = popOperand();
char operator = popOperator();
pushOperand(lOperand + rOperand);
}
private int popOperand()
{
return operands[--idxOfOperands];
}
private char popOperator()
{
return operators[--idxOfOperators];
}- 抽取processOperator()和processOperand()方法，使代码更清晰并处于同一层次。
public void process(char c)
{
if(isDigit(c))
{
processOperand(c);
}
else
{
processOperator(c);
}
}
private void processOperand(char c)
{
pushOperand(toInt(c));
}
private void processOperator(char c)
{
if(notEmptyOperatorStack())
{
calcOnce();
}
pushOperator(c);
}驱动出当前操作符“+”和栈顶操作符“*”的条件判断。
public void test_num_plus_num_multiply()
{
dsp.process('3');
dsp.process('+');
dsp.process('2');
dsp.process('*');
assertEquals(asList(3, 2), dsp.dumpOperandStack());
assertEquals(asList('+', '*'), dsp.dumpOperatorStack());
} private void processOperator(char c)
{
if(notEmptyOperatorStack())
{
if(c == '*' && operators[idxOfOperators - 1] == '+')
{
}
else
{
calcOnce();
}
}
pushOperator(c);
}抽取topOperator()方法。
private void processOperator(char c)
{
if(notEmptyOperatorStack())
{
if(c == '*' && topOperator() == '+')
{
}
else
{
calcOnce();
}
}
pushOperator(c);
}
private char topOperator()
{
return operators[idxOfOperators - 1];
}驱动出apply和乘法计算。
public void test_num_multiply_num_multiply()
{
dsp.process('3');
dsp.process('*');
dsp.process('2');
dsp.process('*');
assertEquals(asList(6), dsp.dumpOperandStack());
assertEquals(asList('*'), dsp.dumpOperatorStack());
} private void calcOnce()
{
int rOperand = popOperand();
int lOperand = popOperand();
char operator = popOperator();
int result = 0; // Temporarily
switch(operator)
{
case '+':
result = lOperand + rOperand;
break;
case '*':
result = lOperand * rOperand;
break;
default:
break;
}
pushOperand(result);
}- 抽取apply()方法。
private void calcOnce()
{
int rOperand = popOperand();
int lOperand = popOperand();
char operator = popOperator();
int result = apply(operator, lOperand, rOperand);
pushOperand(result);
}
private int apply(char operator, int lOperand, int rOperand)
{
int result = 0; //TODO
switch(operator)
{
case '+':
result = lOperand + rOperand;
break;
case '*':
result = lOperand * rOperand;
break;
default:
break;
}
return result;
}- 内联calcOnce()中的result局部变量。
private void calcOnce()
{
int rOperand = popOperand();
int lOperand = popOperand();
char operator = popOperator();
pushOperand(apply(operator, lOperand, rOperand));
}- 改进apply()方法内部实现。定义一个操作符和操作函数的映射。
import java.util.Map;
import java.util.HashMap;
import java.util.function.BiFunction;
private static Map<Character, BiFunction<Integer, Integer, Integer>> operatorAndFuncMap = null;
static
{
operatorAndFuncMap = new HashMap<>();
operatorAndFuncMap.put('+', (x, y) -> x + y);
operatorAndFuncMap.put('*', (x, y) -> x * y);
}
private int apply(char operator, int lOperand, int rOperand)
{
return operatorAndFuncMap.get(operator).apply(lOperand, rOperand);
}测试用例直接测试通过，按照双栈算法描述重构代码。
以目前的产品代码，这个测试用例是可以直接测试通过的。
public void test_num_multiply_num_plus()
{
dsp.process('3');
dsp.process('*');
dsp.process('2');
dsp.process('+');
assertEquals(asList(6), dsp.dumpOperandStack());
assertEquals(asList('+'), dsp.dumpOperatorStack());
}无。
双栈算法描述中有一句话：如果操作符栈不为空且当前操作符的优先级不高于栈顶操作符优先级时，计算一次。按照双栈算法描述重构processOperator()方法。
定义一个操作符和优先级的映射，将操作符优先级的比较转化为数的大小比较。
private static Map<Character, Integer> operatorAndPriorityMap = null;
static
{
operatorAndPriorityMap = new HashMap<>();
operatorAndPriorityMap.put('+', 1);
operatorAndPriorityMap.put('*', 2);
}
private void processOperator(char c)
{
if(notEmptyOperatorStack() && notPriorTo(c, topOperator()))
{
calcOnce();
}
pushOperator(c);
}
private boolean notPriorTo(char operator1, char operator2)
{
return operatorAndPriorityMap.get(operator1) <= operatorAndPriorityMap.get(operator2);
}继续改进notPriorTo()方法。
private boolean notPriorTo(char operator1, char operator2)
{
return priority(operator1) <= priority(operator2);
}
private int priority(char operator)
{
return operatorAndPriorityMap.get(operator);
}驱动出while{calcOnce}。
public void test_num_plus_num_multiply_num_plus()
{
dsp.process('3');
dsp.process('+');
dsp.process('2');
dsp.process('*');
dsp.process('3');
dsp.process('+');
assertEquals(asList(9), dsp.dumpOperandStack());
assertEquals(asList('+'), dsp.dumpOperatorStack());
} private void processOperator(char c)
{
while(notEmptyOperatorStack() && notPriorTo(c, topOperator()))
{
calcOnce();
}
pushOperator(c);
}无。
驱动出“-”的优先级映射。
public void test_num_plus_num_subtract()
{
dsp.process('3');
dsp.process('+');
dsp.process('2');
dsp.process('-');
assertEquals(asList(5), dsp.dumpOperandStack());
assertEquals(asList('-'), dsp.dumpOperatorStack());
} private static Map<Character, Integer> operatorAndPriorityMap = null;
static
{
operatorAndPriorityMap = new HashMap<>();
operatorAndPriorityMap.put('+', 1);
operatorAndPriorityMap.put('-', 1);
operatorAndPriorityMap.put('*', 2);
}无。
驱动出“-”的计算函数映射。
public void test_num_subtract_num_plus()
{
dsp.process('3');
dsp.process('-');
dsp.process('2');
dsp.process('+');
assertEquals(asList(1), dsp.dumpOperandStack());
assertEquals(asList('+'), dsp.dumpOperatorStack());
} private static Map<Character, BiFunction<Integer, Integer, Integer>> operatorAndFuncMap = null;
static
{
operatorAndFuncMap = new HashMap<>();
operatorAndFuncMap.put('+', (x, y) -> x + y);
operatorAndFuncMap.put('-', (x, y) -> x - y);
operatorAndFuncMap.put('*', (x, y) -> x * y);
}无。
驱动出“/”的优先级映射。
public void test_num_subtract_num_divide()
{
dsp.process('4');
dsp.process('-');
dsp.process('2');
dsp.process('/');
assertEquals(asList(4, 2), dsp.dumpOperandStack());
assertEquals(asList('-', '/'), dsp.dumpOperatorStack());
} private static Map<Character, BiFunction<Integer, Integer, Integer>> operatorAndFuncMap = null;
static
{
operatorAndFuncMap = new HashMap<>();
operatorAndFuncMap.put('+', (x, y) -> x + y);
operatorAndFuncMap.put('-', (x, y) -> x - y);
operatorAndFuncMap.put('*', (x, y) -> x * y);
}无。
驱动出“/”的计算函数映射。
public void test_num_divide_num_plus()
{
dsp.process('4');
dsp.process('/');
dsp.process('2');
dsp.process('+');
assertEquals(asList(2), dsp.dumpOperandStack());
assertEquals(asList('+'), dsp.dumpOperatorStack());
} private static Map<Character, BiFunction<Integer, Integer, Integer>> operatorAndFuncMap = null;
static
{
operatorAndFuncMap = new HashMap<>();
operatorAndFuncMap.put('+', (x, y) -> x + y);
operatorAndFuncMap.put('-', (x, y) -> x - y);
operatorAndFuncMap.put('*', (x, y) -> x * y);
operatorAndFuncMap.put('/', (x, y) -> x / y);
}无。
DoubleStackProcessor需要为Expression提供一个获取双栈算法最终处理结果的result()方法。根据双栈算法，当表达式解析到结尾以后，双栈会有三种状态：
- 第一种状态：操作符栈为空，操作数栈只有一个操作数。这是最简单的一种状态，只需要从操作数栈中pop出这个操作数即可，双栈最终均为空。
- 第二种状态：操作符栈有一个操作符，操作数栈有两个操作数。这时，只需要做一次calcOnce，双栈状态就变成了第一种状态，只需要从操作数栈中pop出这个操作数即可，双栈最终均为空。
- 第三种状态：操作符栈有两个操作符，操作数栈有三个操作数。这时，做两次calcOnce，双栈状态就变成了第一种状态，只需要从操作数栈中pop出这个操作数即可，双栈最终均为空。
先来处理第一种状态，驱动出result()方法。
public void test_result_num()
{
dsp.process('3');
assertEquals(3, dsp.result());
assertEquals(asList(), dsp.dumpOperandStack());
assertEquals(asList(), dsp.dumpOperatorStack());
} public int result()
{
return popOperand();
}无。
再来处理第二种状态，驱动出result()方法中的if{calcOnce}。
public void test_result_calc_once()
{
dsp.process('1');
dsp.process('+');
dsp.process('2');
assertEquals(3, dsp.result());
assertEquals(asList(), dsp.dumpOperandStack());
assertEquals(asList(), dsp.dumpOperatorStack());
} public int result()
{
if(notEmptyOperatorStack())
{
calcOnce();
}
return popOperand();
}抽取calc()方法。
public int result()
{
calc();
return popOperand();
}
private void calc()
{
if(notEmptyOperatorStack())
{
calcOnce();
}
}最后处理第三种状态，驱动出result()方法中的while{calcOnce}。
public void test_result_calc_twice()
{
dsp.process('1');
dsp.process('+');
dsp.process('2');
dsp.process('*');
dsp.process('3');
assertEquals(7, dsp.result());
assertEquals(asList(), dsp.dumpOperandStack());
assertEquals(asList(), dsp.dumpOperatorStack());
}将calc()方法中的if改为while。
private void calc()
{
while(notEmptyOperatorStack())
{
calcOnce();
}
}无。
1. "3" (驱动出Expression的主体代码)
2. "2*(1+2)" (驱动出Context和括号相关的代码)
驱动出Expression的主体代码。
因为最终要实现括号相关的需求，括号中间的表达式称为“子表达式”。无论是表达式还是子表达式都应该拥有各自的Expression对象。所以将表达式字符串作为Expression的构造参数。
public class ExpressionTest extends TestCase
{
public void test_num()
{
Expression expr = new Expression("3");
assertEquals(3, expr.eval());
}
}从构造函数传入的表达式字符串expr作为Expression的成员变量。每个表达式或子表达式都应该拥有自己的DoubleStackProcessor对象实例，所以DoubleStackProcessor dsp对象实例也作为Expression的成员变量。另外，还需要记住读取表达式字符串的当前位置，所以curIdx也作为Expression的成员变量。
public class Expression
{
private String expr;
private int curIdx;
private DoubleStackProcessor dsp;
public Expression(String expr)
{
this.expr = expr;
this.curIdx = 0;
this.dsp = new DoubleStackProcessor();
}
public int eval()
{
while(curIdx < expr.length())
{
dsp.process(expr.charAt(curIdx++));
}
return dsp.result();
}
}- 抽取exprNotEnd()方法。
public int eval()
{
while(exprNotEnd())
{
dsp.process(expr.charAt(curIdx++));
}
return dsp.result();
}
private boolean exprNotEnd()
{
return curIdx < expr.length();
}- 抽取nextChar()方法。
public int eval()
{
while(exprNotEnd())
{
dsp.process(nextChar());
}
return dsp.result();
}
private char nextChar()
{
return expr.charAt(curIdx++);
}驱动出Context和括号相关的代码。
public void test_expr_has_parentheses()
{
Expression expr = new Expression("2*(1+2)");
assertEquals(6, expr.eval());
}表达式中有括号就意味着表达式可以嵌套，实现中肯定会包含递归调用。
首先，在整个递归调用中，需要一直准确地记录读取表达式字符串的当前位置(curIdx)。但在Java语言中int类型的curIdx是无法在递归调用中传递的，所以引入一个Context对象，包含curIdx。
其次，递归调用时Expression的构造方法肯定要传入子表达式字符串(expr)，所以把expr和curIdx封装为Context对象。
暂时注释掉上面的括号相关的测试用例，增加Context相关的测试用例。
public void test_expr_context()
{
Expression expr = new Expression(new Context("3", 0));
assertEquals(3, expr.eval());
}增加Context类。
class Context
{
private String expr;
private int curIdx;
Context(String expr, int curIdx)
{
this.expr = expr;
this.curIdx = curIdx;
}
}根据《重构》中的“依恋情结”章节的描述，如果某个类的某段代码中引用的所有变量或方法都来自于另一个类，意味着这段代码放在那个类中更合适。据此，将Expression类中的exprNotEnd()和nextChar()挪到Context类中。
class Context
{
private String expr;
private int curIdx;
Context(String expr, int curIdx)
{
this.expr = expr;
this.curIdx = curIdx;
}
boolean exprNotEnd()
{
return curIdx < expr.length();
}
char nextChar()
{
return expr.charAt(curIdx++);
}
}围绕Context修改Expression类。
public class Expression
{
private Context ctx;
private DoubleStackProcessor dsp;
public Expression(String expr)
{
this(new Context(expr, 0));
}
Expression(Context ctx)
{
this.ctx = ctx;
this.dsp = new DoubleStackProcessor();
}
public int eval()
{
while(ctx.exprNotEnd())
{
dsp.process(ctx.nextChar());
}
return dsp.result();
}
}无。
放开之前注释的括号相关的测试用例。
public void test_expr_has_parentheses()
{
Expression expr = new Expression("2*(1+2)");
assertEquals(6, expr.eval());
}修改Expression类的eval()方法。
- 当前字符为“(”时，说明接下来是一个子表达式，把上下文ctx传给子表达式对应的新的Expression对象，eval()出的结果是子表达式的计算结果，入当前表达式操作数栈。
- 当前字符为“)”时，说明子表达式即将结束，此时的dsp是子表达式的dsp，调用dsp.result()得到子表达式的计算结果并返回。
- 其他情况下，属于一个表达式内部处理，交给自己的dsp处理即可。
- 代码看上去是平面的，但运行起来是立体的，注意仔细体会。
public int eval()
{
while(ctx.exprNotEnd())
{
char c = ctx.nextChar();
if('(' == c)
{
dsp.pushOperand(new Expression(ctx).eval());
}
else if(')' == c)
{
return dsp.result();
}
else
{
dsp.process(c);
}
}
return dsp.result();
}注意，要修改DoubleStackProcessor类pushOperand()方法的可见性，由private改为包可访问。
void pushOperand(int operand)
{
operands[idxOfOperands++] = operand;
}无。
至此四则运算的代码已全部实现。这里只是用一些复杂的测试用例验证一下。
public void test_expr_final()
{
Expression expr = new Expression("((1+2)+1)*2");
assertEquals(8, expr.eval());
expr = new Expression("(1+(1+2))*2");
assertEquals(8, expr.eval());
expr = new Expression("(2-(1-2))*3+(2-(2+1))*3");
assertEquals(6, expr.eval());
}import junit.framework.Test;
import junit.framework.TestSuite;
public class AllTests
{
public static Test suite()
{
TestSuite suite = new TestSuite(AllTests.class.getName());
//$JUnit-BEGIN$
suite.addTestSuite(DoubleStackProcessorTest.class);
suite.addTestSuite(ExpressionTest.class);
//$JUnit-END$
return suite;
}
}请学员先总结一下。
- TDD三步军规、小步。
- 测试：
- 始终选择当前最有价值的测试用例；
- 测试三段式：Arrange、Act、Assert；
- 不要忘了测试代码也需要重构；
- 合理使用TestSuite。
- 规范：
- 代码目录规范：testsrc、src；
- 类名命名规范：XyzTest、Xyz。
- 每次修改代码，都运行一下测试用例，注意红绿绿的节奏。
- 写代码应做到：
- 简洁明了：概念定义清晰、准确；简明清晰地表达语义；
- 表达到位：层次分明、表现意图；跟问题领域的概念、规则相吻合；
- 安全可靠：状态、时序管理得当；具有必要的测试安全网络。
代码包路径：fayelab.tdd.arithmetic.doublestack.original
- 【必选】表达式支持“取余”操作符“%”，优先级与“*、/”一样。
- 【可选】表达式支持多位正整数。
- 【可选】表达式支持“幂”操作符“**”，优先级比“*、/”高。
- 【可选】表达式支持负整数。
表达式支持“取余”操作符“%”，优先级与“*、/”一样。
代码包路径：fayelab.tdd.arithmetic.doublestack.rem
测试用例如下：
15. 3+2% (驱动出“%”的优先级映射)
16. 3%2+ (驱动出“%”的计算函数映射)
驱动出“%”的优先级映射。
DoubleStackProcessorTest.java
public void test_num_plus_num_rem()
{
dsp.process('3');
dsp.process('+');
dsp.process('2');
dsp.process('%');
assertEquals(asList(3, 2), dsp.dumpOperandStack());
assertEquals(asList('+', '%'), dsp.dumpOperatorStack());
}DoubleStackProcessor.java
private static Map<Character, Integer> operatorAndPriorityMap = null;
static
{
operatorAndPriorityMap = new HashMap<>();
operatorAndPriorityMap.put('+', 1);
operatorAndPriorityMap.put('-', 1);
operatorAndPriorityMap.put('*', 2);
operatorAndPriorityMap.put('/', 2);
operatorAndPriorityMap.put('%', 2);
}无。
驱动出“%”的计算函数映射。
DoubleStackProcessorTest.java
public void test_num_rem_num_plus()
{
dsp.process('3');
dsp.process('%');
dsp.process('2');
dsp.process('+');
assertEquals(asList(1), dsp.dumpOperandStack());
assertEquals(asList('+'), dsp.dumpOperatorStack());
}DoubleStackProcessor.java
private static Map<Character, BiFunction<Integer, Integer, Integer>> operatorAndFuncMap = null;
static
{
operatorAndFuncMap = new HashMap<>();
operatorAndFuncMap.put('+', (x, y) -> x + y);
operatorAndFuncMap.put('-', (x, y) -> x - y);
operatorAndFuncMap.put('*', (x, y) -> x * y);
operatorAndFuncMap.put('/', (x, y) -> x / y);
operatorAndFuncMap.put('%', (x, y) -> x % y);
}无。
表达式支持多位正整数。
代码包路径：fayelab.tdd.arithmetic.doublestack.multidigit
由Expression类完成“多位正整数”操作数的解析。
DoubleStackProcessor类的process()方法不能只接受一个字符，改为接受字符串。
先后分别修改DoubleStackProcessor和Expression的测试代码和产品代码。
为了做到小步，先把DoubleStackProcessorTest类中原有的测试用例方法名都加“_2”，等全部改好了以后，再删掉这些不再有用的测试用例。
测试用例如下：
1. 12 (新增process(String item)方法和toInt(String str)方法)
2. 12+ (process(String item)增加allDigits判断分支。
新增allDigits()方法和toChar()方法)
3. 12+34+ (新增processOperand(String item)和processOperator(String item)
方法。其中processsOperator()中增加操作符栈是否为空的判断分支。)
4. 12+34* (processOperator()方法增加notPriorTo()判断分支。)
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{calcOnce})
14. "12" (测试用例直接测试通过)
15. "12+34" (测试用例直接测试通过)
16. "12+34*10" (测试用例直接测试通过)
DoubleStackProcessor类中先保留process(char c)方法，新增process(String item)方法，等全部改好了以后，再删掉process(char c)方法。这样对Expression的影响也比较小。
public void test_num()
{
dsp.process("12");
assertEquals(asList(12), dsp.dumpOperandStack());
assertEquals(asList(), dsp.dumpOperatorStack());
}新增process(String item)方法和toInt(String str)方法。
public void process(String item)
{
pushOperand(toInt(item));
}
private int toInt(String str)
{
return Integer.parseInt(str);
}无。
public void test_num_plus()
{
dsp.process("12");
dsp.process("+"); //not operator char but string
assertEquals(asList(12), dsp.dumpOperandStack());
assertEquals(asList('+'), dsp.dumpOperatorStack());
}process(String item)增加allDigits判断分支。新增allDigits()方法和toChar()方法。
public void process(String item)
{
if(allDigits(item))
{
pushOperand(toInt(item));
}
else
{
pushOperator(toChar(item));
}
}
private boolean allDigits(String str)
{
return Pattern.matches("\\d+", str);
}
private char toChar(String oneCharStr)
{
return oneCharStr.charAt(0);
}无。
public void test_num_plus_num_plus()
{
dsp.process("12");
dsp.process("+");
dsp.process("34");
dsp.process("+");
assertEquals(asList(46), dsp.dumpOperandStack());
assertEquals(asList('+'), dsp.dumpOperatorStack());
}新增processOperand(String item)和processOperator(String item)方法。其中processsOperator()中增加操作符栈是否为空的判断分支。
public void process(String item)
{
if(allDigits(item))
{
processOperand(item);
}
else
{
processOperator(item);
}
}
private void processOperand(String item)
{
pushOperand(toInt(item));
}
private void processOperator(String item)
{
if(notEmptyOperatorStack())
{
calcOnce();
}
pushOperator(toChar(item));
}无。
public void test_num_plus_num_multiply()
{
dsp.process("12");
dsp.process("+");
dsp.process("34");
dsp.process("*");
assertEquals(asList(12, 34), dsp.dumpOperandStack());
assertEquals(asList('+', '*'), dsp.dumpOperatorStack());
} processOperator()方法增加notPriorTo()判断分支。
private void processOperator(String item)
{
char curChar = toChar(item);
if(notEmptyOperatorStack() && notPriorTo(curChar, topOperator()))
{
calcOnce();
}
pushOperator(curChar);
} 无。
到这里，以下测试用例全部可以直接测试通过。
5. 12*10*
6. 12*10+
7. 12+34-
8. 34-12+
9. 34-12/
10. 24/12+
11. 12+34%
12. 34%12+
public void test_num_multiply_num_multiply()
{
dsp.process("12");
dsp.process("*");
dsp.process("10");
dsp.process("*");
assertEquals(asList(120), dsp.dumpOperandStack());
assertEquals(asList('*'), dsp.dumpOperatorStack());
}
public void test_num_multiply_num_plus()
{
dsp.process("12");
dsp.process("*");
dsp.process("10");
dsp.process("+");
assertEquals(asList(120), dsp.dumpOperandStack());
assertEquals(asList('+'), dsp.dumpOperatorStack());
}
public void test_num_plus_num_subtract()
{
dsp.process("12");
dsp.process("+");
dsp.process("34");
dsp.process("-");
assertEquals(asList(46), dsp.dumpOperandStack());
assertEquals(asList('-'), dsp.dumpOperatorStack());
}
public void test_num_subtract_num_plus()
{
dsp.process("34");
dsp.process("-");
dsp.process("12");
dsp.process("+");
assertEquals(asList(22), dsp.dumpOperandStack());
assertEquals(asList('+'), dsp.dumpOperatorStack());
}
public void test_num_subtract_num_divide()
{
dsp.process("34");
dsp.process("-");
dsp.process("12");
dsp.process("/");
assertEquals(asList(34, 12), dsp.dumpOperandStack());
assertEquals(asList('-', '/'), dsp.dumpOperatorStack());
}
public void test_num_divide_num_plus()
{
dsp.process("24");
dsp.process("/");
dsp.process("12");
dsp.process("+");
assertEquals(asList(2), dsp.dumpOperandStack());
assertEquals(asList('+'), dsp.dumpOperatorStack());
}
public void test_num_plus_num_rem()
{
dsp.process("12");
dsp.process("+");
dsp.process("34");
dsp.process("%");
assertEquals(asList(12, 34), dsp.dumpOperandStack());
assertEquals(asList('+', '%'), dsp.dumpOperatorStack());
}
public void test_num_rem_num_plus()
{
dsp.process("34");
dsp.process("%");
dsp.process("12");
dsp.process("+");
assertEquals(asList(10), dsp.dumpOperandStack());
assertEquals(asList('+'), dsp.dumpOperatorStack());
} public void test_num_plus_num_multiply_num_plus()
{
dsp.process("12");
dsp.process("+");
dsp.process("10");
dsp.process("*");
dsp.process("34");
dsp.process("+");
assertEquals(asList(352), dsp.dumpOperandStack());
assertEquals(asList('+'), dsp.dumpOperatorStack());
}驱动出while{calcOnce}。
private void processOperator(String item)
{
char curChar = toChar(item);
while(notEmptyOperatorStack() && notPriorTo(curChar, topOperator()))
{
calcOnce();
}
pushOperator(curChar);
}无。
到这里，以下测试用例全部可以直接测试通过。
14. "12"
15. "12+34"
16. "12+34*10"
public void test_result_num()
{
dsp.process("12");
assertEquals(12, dsp.result());
assertEquals(asList(), dsp.dumpOperandStack());
assertEquals(asList(), dsp.dumpOperatorStack());
}
public void test_result_calc_once()
{
dsp.process("12");
dsp.process("+");
dsp.process("34");
assertEquals(46, dsp.result());
assertEquals(asList(), dsp.dumpOperandStack());
assertEquals(asList(), dsp.dumpOperatorStack());
}
public void test_result_calc_twice()
{
dsp.process("12");
dsp.process("+");
dsp.process("34");
dsp.process("*");
dsp.process("10");
assertEquals(352, dsp.result());
assertEquals(asList(), dsp.dumpOperandStack());
assertEquals(asList(), dsp.dumpOperatorStack());
}删除DoubleStackProcessorTest类中所有不再有用的测试用例，即方法名以“_2”结尾的测试用例。
由于Expression类尚未修改，DoubleStackProcess类中的process(char c)方法暂时不能删除。
为了做到小步，先把ExpressionTest类中原有的测试用例方法名都加“_2”，等全部改好了以后，再删掉这些不再有用的测试用例。同时，把Expression类原有的eval()方法改名为eval2()。
测试用例如下：
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()中增加右括号紧跟右括号的处理逻辑)
驱动出eval()中的数字缓存逻辑。
public void test_num()
{
Expression expr = new Expression("12");
assertEquals(12, expr.eval());
} public int eval()
{
StringBuffer digitBuffer = new StringBuffer();
while(ctx.exprNotEnd())
{
digitBuffer.append(ctx.nextChar());
}
dsp.process(digitBuffer.toString());
return dsp.result();
}无。
eval()中增加字符是数字或操作符号的判断分支。
public void test_expr_has_one_operator()
{
Expression expr = new Expression("12+34");
assertEquals(46, expr.eval());
}操作数出现在操作符之前和表达式结尾。
public int eval()
{
StringBuffer digitBuffer = new StringBuffer();
while(ctx.exprNotEnd())
{
char c = ctx.nextChar();
if(isDigit(c))
{
digitBuffer.append(c);
}
else
{
dsp.process(digitBuffer.toString());
digitBuffer = new StringBuffer();
dsp.process(String.valueOf(c));
}
}
dsp.process(digitBuffer.toString());
return dsp.result();
}
private boolean isDigit(char c)
{
return '0' <= c && c <= '9';
}无。
以目前的产品代码，这个测试用例是可以直接测试通过的。
public void test_expr_has_multiple_operators()
{
Expression expr = new Expression("12+34*10");
assertEquals(352, expr.eval());
}无。
无。
eval()中增加右括号后面紧跟着操作符的处理逻辑。此时digitBuffer长度为0。
操作数除了出现在操作符之前和表达式结尾，还可以出现在子表达式结尾，即“)”之前。
public void test_expr_with_right_parenthesis_followed_by_an_operator()
{
Expression expr = new Expression("(12+34)*10");
assertEquals(460, expr.eval());
} public int eval()
{
StringBuffer digitBuffer = new StringBuffer();
while(ctx.exprNotEnd())
{
char c = ctx.nextChar();
if('(' == c)
{
dsp.pushOperand(new Expression(ctx).eval());
}
else if(')' == c)
{
dsp.process(digitBuffer.toString());
return dsp.result();
}
else
{
if(isDigit(c))
{
digitBuffer.append(c);
}
else
{
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
digitBuffer = new StringBuffer();
} //else digitBuffer.length() == 0 when right parenthesis followed by an operator
dsp.process(String.valueOf(c));
}
}
}
dsp.process(digitBuffer.toString());
return dsp.result();
}无。
eval()中增加表达式以右括号结尾的处理逻辑。此时digitBuffer长度为0。
public void test_expr_ends_with_right_parenthesis()
{
Expression expr = new Expression("10*(12+34)");
assertEquals(460, expr.eval());
} public int eval()
{
StringBuffer digitBuffer = new StringBuffer();
while(ctx.exprNotEnd())
{
char c = ctx.nextChar();
if('(' == c)
{
dsp.pushOperand(new Expression(ctx).eval());
}
else if(')' == c)
{
dsp.process(digitBuffer.toString());
return dsp.result();
}
else
{
if(isDigit(c))
{
digitBuffer.append(c);
}
else
{
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
digitBuffer = new StringBuffer();
} //else digitBuffer.length() == 0 when right parenthesis followed by an operator
dsp.process(String.valueOf(c));
}
}
}
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
} //else digitBuffer.length() == 0 when expr ends with right parenthesis
return dsp.result();
}无。
eval()中增加右括号紧跟右括号的处理逻辑。此时digitBuffer长度为0。
public void test_expr_with_right_parenthesis_followed_by_right_parenthesis()
{
Expression expr = new Expression("(48-(12+34))*10");
assertEquals(20, expr.eval());
Expression expr2 = new Expression("10*(48-(12+34))");
assertEquals(20, expr2.eval());
} public int eval()
{
StringBuffer digitBuffer = new StringBuffer();
while(ctx.exprNotEnd())
{
char c = ctx.nextChar();
if('(' == c)
{
dsp.pushOperand(new Expression(ctx).eval());
}
else if(')' == c)
{
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
} //else digitBuffer.length() == 0 when right parenthesis followed by right parenthesis
return dsp.result();
}
else
{
if(isDigit(c))
{
digitBuffer.append(c);
}
else
{
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
digitBuffer = new StringBuffer();
} //else digitBuffer.length() == 0 when right parenthesis followed by an operator
dsp.process(String.valueOf(c));
}
}
}
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
} //else digitBuffer.length() == 0 when expr ends with right parenthesis
return dsp.result();
}无。
至此多位正整数相关代码已全部实现。这里只是用一些复杂的测试用例验证一下。
public void test_expr_with_nested_parentheses()
{
Expression expr = new Expression("((10+21)+34)*20");
assertEquals(1300, expr.eval());
Expression expr2 = new Expression("(50-(12+34))*20");
assertEquals(80, expr2.eval());
Expression expr3 = new Expression("((11+23)%11)*20");
assertEquals(20, expr3.eval());
Expression expr4 = new Expression("(12-(15-12))*10/(24-(12+10))/3");
assertEquals(15, expr4.eval());
Expression expr5 = new Expression("(100-(1920-1900))*2/(24-(12+10))/2");
assertEquals(40, expr5.eval());
}先删除ExpressionTest类中所有不再有用的测试用例，即方法名以“_2”结尾的测试用例。
再删除Expression、DoubleStackProcess类中所有不再有用的产品代码。
表达式支持“幂”操作符“**”，优先级比“*、/”高。
代码包路径：fayelab.tdd.arithmetic.doublestack.pow
由Expression类完成类似“**”这种字符长度超过1的操作符的解析。
DoubleStackProcessor类的操作符堆栈的元素类型需要由char改为String。
先将操作符堆栈的元素类型由char改为String，再增加“幂”操作符功能。
先后分别修改DoubleStackProcessor和Expression的测试代码和产品代码。
将操作符堆栈的元素类型由char改为String。
为了做到小步，先把DoubleStackProcessorTest类中原有的测试用例方法名都加“_2”，等全部改好了以后，再删掉这些不再有用的测试用例。
测试用例如下：
1. 12 (新增process(String item)方法)
2. 12+ (process(String item)增加allDigits判断分支。
操作符堆栈的元素类型需要由char改为String)
3. 12+34+ (测试用例直接测试通过)
4. 12+34* (测试用例直接测试通过)
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+ (测试用例直接测试通过)
14. "12" (测试用例直接测试通过)
15. "12+34" (测试用例直接测试通过)
16. "12+34*10" (测试用例直接测试通过)
####### 8.3.1.1.2.1.1 Add a Test 先把DoubleStackProcessor类的process(String item)方法改名为process_2(String item)，等全部改好了以后，再删掉process_2(String item)方法。这样对Expression的影响也比较小。
public void test_num()
{
dsp.process("12");
assertEquals(asList(12), dsp.dumpOperandStack());
assertEquals(asList(), dsp.dumpOperatorStack());
}####### 8.3.1.1.2.1.2 Write the Code 新增process(String item)方法。因为操作数相关的逻辑不用修改，所以在process(String item)方法中直接调用processOperand()方法即可。
public void process(String item)
{
processOperand(item);
}####### 8.3.1.1.2.1.3 Refactor the Code 无。
####### 8.3.1.1.2.2.1 Add a Test
public void test_num_plus()
{
dsp.process("12");
dsp.process("+"); //not operator char but string
assertEquals(asList(12), dsp.dumpOperandStack());
assertEquals(asList("+"), dsp.dumpOperatorStack());
}####### 8.3.1.1.2.2.2 Write the Code 先在process(String item)中增加allDigits判断分支。
public void process(String item)
{
if(allDigits(item))
{
processOperand(item);
}
else
{
processOperator(item);
}
}再将操作符堆栈的元素类型由char改为String。
重命名DoubleStackProcessor类以下成员变量，在原有变量名后加上“_2”：
- operatorAndFuncMap -> operatorAndFuncMap_2
- operatorAndPrioritiyMap -> operatorAndPrioritiyMap_2
新增操作符数据类型为字符串的operatorAndFuncMap和operatorAndPrioritiyMap。
private static Map<String, BiFunction<Integer, Integer, Integer>> operatorAndFuncMap = null;
static
{
operatorAndFuncMap = new HashMap<>();
operatorAndFuncMap.put("+", (x, y) -> x + y);
operatorAndFuncMap.put("-", (x, y) -> x - y);
operatorAndFuncMap.put("*", (x, y) -> x * y);
operatorAndFuncMap.put("/", (x, y) -> x / y);
operatorAndFuncMap.put("%", (x, y) -> x % y);
}
private static Map<String, Integer> operatorAndPriorityMap = null;
static
{
operatorAndPriorityMap = new HashMap<>();
operatorAndPriorityMap.put("+", 1);
operatorAndPriorityMap.put("-", 1);
operatorAndPriorityMap.put("*", 2);
operatorAndPriorityMap.put("/", 2);
operatorAndPriorityMap.put("%", 2);
}将DoubleStackProcessor类的成员变量operators重命名为operators_2，新增操作符数据类型为字符串的operators。
private String[] operators = new String[OPERATOR_STACK_MAX_SIZE];重命名以下方法，在原有方法名后加上“_2”：
- processOperator() -> processOperator_2()
- notPriorTo() -> notPriorTo_2()
- priority() -> priority_2()
- topOperator() -> topOperator_2()
- calcOnce() -> calcOnce_2()
- popOperator() -> popOperator_2()
- apply() -> apply_2()
- pushOperator() -> pushOperator_2()
新增processOperator()方法，并在process(String item)方法中调用新增的processOperator()方法。新增的processOperator()方法的主要逻辑和原来的一致，只是原来调用toChar()地方不用再调用toChar()方法。另外，还需要新增notPriorTo()、priority()、topOperator()、calcOnce()、apply()、popOperator()和pushOperator()方法。
public void process(String item)
{
if(allDigits(item))
{
processOperand(item);
}
else
{
processOperator(item);
}
}
private void processOperator(String item)
{
while(notEmptyOperatorStack() && notPriorTo(item, topOperator()))
{
calcOnce();
}
pushOperator(item);
}
private boolean notPriorTo(String operator1, String operator2)
{
return priority(operator1) <= priority(operator2);
}
private int priority(String operator)
{
return operatorAndPriorityMap.get(operator);
}
private String topOperator()
{
return operators[idxOfOperators - 1];
}
private void calcOnce()
{
int rOperand = popOperand();
int lOperand = popOperand();
String operator = popOperator();
pushOperand(apply(operator, lOperand, rOperand));
}
private int apply(String operator, int lOperand, int rOperand)
{
return operatorAndFuncMap.get(operator).apply(lOperand, rOperand);
}
private String popOperator()
{
return operators[--idxOfOperators];
}
private void pushOperator(String operator)
{
operators[idxOfOperators++] = operator;
} 将原来的dumpOperatorStack()方法重命名为dumpOperatorStack_2()。新增dumpOperatorStack()方法，并在新的测试方法中调用新增的dumpOperatorStack()方法。
List<String> dumpOperatorStack()
{
return IntStream.range(0, idxOfOperators).mapToObj(i -> operators[i]).collect(toList());
}####### 8.3.1.1.2.2.3 Refactor the Code 无。
至此DoubleStackProcessor类的操作符堆栈的元素类型由char改为String的修改全部完成，以下测试用例全部可以直接测试通过。
3. 12+34+
4. 12+34*
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+
14. "12"
15. "12+34"
16. "12+34*10"
public void test_num_plus_num_plus()
{
dsp.process("12");
dsp.process("+");
dsp.process("34");
dsp.process("+");
assertEquals(asList(46), dsp.dumpOperandStack());
assertEquals(asList("+"), dsp.dumpOperatorStack());
}
public void test_num_plus_num_multiply()
{
dsp.process("12");
dsp.process("+");
dsp.process("34");
dsp.process("*");
assertEquals(asList(12, 34), dsp.dumpOperandStack());
assertEquals(asList("+", "*"), dsp.dumpOperatorStack());
}
public void test_num_multiply_num_multiply()
{
dsp.process("12");
dsp.process("*");
dsp.process("10");
dsp.process("*");
assertEquals(asList(120), dsp.dumpOperandStack());
assertEquals(asList("*"), dsp.dumpOperatorStack());
}
public void test_num_multiply_num_plus()
{
dsp.process("12");
dsp.process("*");
dsp.process("10");
dsp.process("+");
assertEquals(asList(120), dsp.dumpOperandStack());
assertEquals(asList("+"), dsp.dumpOperatorStack());
}
public void test_num_plus_num_subtract()
{
dsp.process("12");
dsp.process("+");
dsp.process("34");
dsp.process("-");
assertEquals(asList(46), dsp.dumpOperandStack());
assertEquals(asList("-"), dsp.dumpOperatorStack());
}
public void test_num_subtract_num_plus()
{
dsp.process("34");
dsp.process("-");
dsp.process("12");
dsp.process("+");
assertEquals(asList(22), dsp.dumpOperandStack());
assertEquals(asList("+"), dsp.dumpOperatorStack());
}
public void test_num_subtract_num_divide()
{
dsp.process("34");
dsp.process("-");
dsp.process("12");
dsp.process("/");
assertEquals(asList(34, 12), dsp.dumpOperandStack());
assertEquals(asList("-", "/"), dsp.dumpOperatorStack());
}
public void test_num_divide_num_plus()
{
dsp.process("24");
dsp.process("/");
dsp.process("12");
dsp.process("+");
assertEquals(asList(2), dsp.dumpOperandStack());
assertEquals(asList("+"), dsp.dumpOperatorStack());
}
public void test_num_plus_num_rem()
{
dsp.process("12");
dsp.process("+");
dsp.process("34");
dsp.process("%");
assertEquals(asList(12, 34), dsp.dumpOperandStack());
assertEquals(asList("+", "%"), dsp.dumpOperatorStack());
}
public void test_num_rem_num_plus()
{
dsp.process("34");
dsp.process("%");
dsp.process("12");
dsp.process("+");
assertEquals(asList(10), dsp.dumpOperandStack());
assertEquals(asList("+"), dsp.dumpOperatorStack());
}
public void test_num_plus_num_multiply_num_plus()
{
dsp.process("12");
dsp.process("+");
dsp.process("10");
dsp.process("*");
dsp.process("34");
dsp.process("+");
assertEquals(asList(352), dsp.dumpOperandStack());
assertEquals(asList("+"), dsp.dumpOperatorStack());
}
public void test_result_num()
{
dsp.process("12");
assertEquals(12, dsp.result());
assertEquals(asList(), dsp.dumpOperandStack());
assertEquals(asList(), dsp.dumpOperatorStack());
}
public void test_result_calc_once()
{
dsp.process("12");
dsp.process("+");
dsp.process("34");
assertEquals(46, dsp.result());
assertEquals(asList(), dsp.dumpOperandStack());
assertEquals(asList(), dsp.dumpOperatorStack());
}
public void test_result_calc_twice()
{
dsp.process("12");
dsp.process("+");
dsp.process("34");
dsp.process("*");
dsp.process("10");
assertEquals(352, dsp.result());
assertEquals(asList(), dsp.dumpOperandStack());
assertEquals(asList(), dsp.dumpOperatorStack());
}为了做到小步，先把ExpressionTest类中原有的测试用例方法名都加“_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()中增加右括号紧跟右括号的处理逻辑)
驱动出eval()中的数字缓存逻辑。
####### 8.3.1.2.2.1.1 Add a Test
public void test_num()
{
Expression expr = new Expression("12");
assertEquals(12, expr.eval());
}####### 8.3.1.2.2.1.2 Write the Code 将DoubleStackProcessor类的result()方法改名为result_2()。将result_2()方法中调用的calc()方法改名为calc_2()。如果一直按照文中的步骤进行小步修改，改名后的calc_2()调用的应该是calcOnce_2()方法。
Expression类新增eval()方法。
public int eval()
{
StringBuffer digitBuffer = new StringBuffer();
while(ctx.exprNotEnd())
{
digitBuffer.append(ctx.nextChar());
}
dsp.process(digitBuffer.toString());
return dsp.result();
}DoubleStackProcessor类新增result()方法。result()方法中调用新增的calc()方法，calc()方法中调用在前面步骤中已经写好的calcOnce()方法。
public int result()
{
calc();
return popOperand();
}
private void calc()
{
while(notEmptyOperatorStack())
{
calcOnce();
}
}####### 8.3.1.2.2.1.3 Refactor the Code 无。
eval()中增加字符是数字或操作符号的判断分支。
####### 8.3.1.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.3.1.2.2.2.2 Write the Code 操作数出现在操作符之前和表达式结尾。
public int eval()
{
StringBuffer digitBuffer = new StringBuffer();
while(ctx.exprNotEnd())
{
char c = ctx.nextChar();
if(isDigit(c))
{
digitBuffer.append(c);
}
else
{
dsp.process(digitBuffer.toString());
digitBuffer = new StringBuffer();
dsp.process(String.valueOf(c));
}
}
dsp.process(digitBuffer.toString());
return dsp.result();
}
private boolean isDigit(char c)
{
return '0' <= c && c <= '9';
}####### 8.3.1.2.2.2.3 Refactor the Code 无。
####### 8.3.1.2.2.3.1 Add a Test 以目前的产品代码，这个测试用例是可以直接测试通过的。
public void test_expr_has_multiple_operators()
{
Expression expr = new Expression("12+34*10");
assertEquals(352, expr.eval());
}####### 8.3.1.2.2.3.2 Write the Code 无。
####### 8.3.1.2.2.3.3 Refactor the Code 无。
eval()中增加右括号后面紧跟着操作符的处理逻辑。此时digitBuffer长度为0。
操作数除了出现在操作符之前和表达式结尾，还可以出现在子表达式结尾，即“)”之前。
####### 8.3.1.2.2.4.1 Add a Test
public void test_expr_with_right_parenthesis_followed_by_an_operator()
{
Expression expr = new Expression("(12+34)*10");
assertEquals(460, expr.eval());
}####### 8.3.1.2.2.4.2 Write the Code
public int eval()
{
StringBuffer digitBuffer = new StringBuffer();
while(ctx.exprNotEnd())
{
char c = ctx.nextChar();
if('(' == c)
{
dsp.pushOperand(new Expression(ctx).eval());
}
else if(')' == c)
{
dsp.process(digitBuffer.toString());
return dsp.result();
}
else
{
if(isDigit(c))
{
digitBuffer.append(c);
}
else
{
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
digitBuffer = new StringBuffer();
} //else digitBuffer.length() == 0 when right parenthesis followed by an operator
dsp.process(String.valueOf(c));
}
}
}
dsp.process(digitBuffer.toString());
return dsp.result();
}####### 8.3.1.2.2.4.3 Refactor the Code 无。
eval()中增加表达式以右括号结尾的处理逻辑。此时digitBuffer长度为0。
####### 8.3.1.2.2.5.1 Add a Test
public void test_expr_ends_with_right_parenthesis()
{
Expression expr = new Expression("10*(12+34)");
assertEquals(460, expr.eval());
}####### 8.3.1.2.2.5.2 Write the Code
public int eval()
{
StringBuffer digitBuffer = new StringBuffer();
while(ctx.exprNotEnd())
{
char c = ctx.nextChar();
if('(' == c)
{
dsp.pushOperand(new Expression(ctx).eval());
}
else if(')' == c)
{
dsp.process(digitBuffer.toString());
return dsp.result();
}
else
{
if(isDigit(c))
{
digitBuffer.append(c);
}
else
{
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
digitBuffer = new StringBuffer();
} //else digitBuffer.length() == 0 when right parenthesis followed by an operator
dsp.process(String.valueOf(c));
}
}
}
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
} //else digitBuffer.length() == 0 when expr ends with right parenthesis
return dsp.result();
}####### 8.3.1.2.2.5.3 Refactor the Code 无。
eval()中增加右括号紧跟右括号的处理逻辑。此时digitBuffer长度为0。
####### 8.3.1.2.2.6.1 Add a Test
public void test_expr_with_right_parenthesis_followed_by_right_parenthesis()
{
Expression expr = new Expression("(48-(12+34))*10");
assertEquals(20, expr.eval());
Expression expr2 = new Expression("10*(48-(12+34))");
assertEquals(20, expr2.eval());
}####### 8.3.1.2.2.6.2 Write the Code
public int eval()
{
StringBuffer digitBuffer = new StringBuffer();
while(ctx.exprNotEnd())
{
char c = ctx.nextChar();
if('(' == c)
{
dsp.pushOperand(new Expression(ctx).eval());
}
else if(')' == c)
{
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
} //else digitBuffer.length() == 0 when right parenthesis followed by right parenthesis
return dsp.result();
}
else
{
if(isDigit(c))
{
digitBuffer.append(c);
}
else
{
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
digitBuffer = new StringBuffer();
} //else digitBuffer.length() == 0 when right parenthesis followed by an operator
dsp.process(String.valueOf(c));
}
}
}
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
} //else digitBuffer.length() == 0 when expr ends with right parenthesis
return dsp.result();
}####### 8.3.1.2.2.6.3 Refactor the Code 无。
至此将操作符堆栈的元素类型由char改为String的修改已全部完成。这里只是用一些复杂的测试用例验证一下。
public void test_expr_with_nested_parentheses()
{
Expression expr = new Expression("((10+21)+34)*20");
assertEquals(1300, expr.eval());
Expression expr2 = new Expression("(50-(12+34))*20");
assertEquals(80, expr2.eval());
Expression expr3 = new Expression("((11+23)%11)*20");
assertEquals(20, expr3.eval());
Expression expr4 = new Expression("(12-(15-12))*10/(24-(12+10))/3");
assertEquals(15, expr4.eval());
Expression expr5 = new Expression("(100-(1920-1900))*2/(24-(12+10))/2");
assertEquals(40, expr5.eval());
}先删除ExpressionTest类中所有不再有用的测试用例，即方法名以“_2”结尾的测试用例。
再删除Expression、DoubleStackProcess类中所有不再有用的产品代码。
支持“幂”操作符“**”。
支持“幂”操作符“**”。
测试用例如下：
17. 12*2** (驱动出“**”的优先级映射)
18. 10**3* (驱动出“**”的计算函数映射)
驱动出“**”的优先级映射。
####### 8.3.2.1.2.1 Add a Test
public void test_num_multiply_num_pow()
{
dsp.process("12");
dsp.process("*");
dsp.process("2");
dsp.process("**");
assertEquals(asList(12, 2), dsp.dumpOperandStack());
assertEquals(asList("*", "**"), dsp.dumpOperatorStack());
}####### 8.3.2.1.2.2 Write the Code
private static Map<String, Integer> operatorAndPriorityMap = null;
static
{
operatorAndPriorityMap = new HashMap<>();
operatorAndPriorityMap.put("+", 1);
operatorAndPriorityMap.put("-", 1);
operatorAndPriorityMap.put("*", 2);
operatorAndPriorityMap.put("/", 2);
operatorAndPriorityMap.put("%", 2);
operatorAndPriorityMap.put("**", 3);
}####### 8.3.2.1.2.3 Refactor the Code 无。
驱动出“**”的计算函数映射。
####### 8.3.2.1.2.2.1 Add a Test
public void test_num_pow_num_multiply()
{
dsp.process("10");
dsp.process("**");
dsp.process("3");
dsp.process("*");
assertEquals(asList(1000), dsp.dumpOperandStack());
assertEquals(asList("*"), dsp.dumpOperatorStack());
}####### 8.3.2.1.2.2.2 Write the Code
private static Map<String, BiFunction<Integer, Integer, Integer>> operatorAndFuncMap = null;
static
{
operatorAndFuncMap = new HashMap<>();
operatorAndFuncMap.put("+", (x, y) -> x + y);
operatorAndFuncMap.put("-", (x, y) -> x - y);
operatorAndFuncMap.put("*", (x, y) -> x * y);
operatorAndFuncMap.put("/", (x, y) -> x / y);
operatorAndFuncMap.put("%", (x, y) -> x % y);
operatorAndFuncMap.put("**", (x, y) -> IntStream.range(0, y).map(i -> x).reduce(1, (m, n) -> m * n));
}####### 8.3.2.1.2.2.3 Refactor the Code 无。
完成类似“**”这种字符长度超过1的操作符的解析。
测试用例如下：
7. "2**3" (驱动出eval()中的操作符字符缓存逻辑以及操作符后面紧跟着数字的处理逻辑)
8. "2**(1+2)" (eval()中增加操作符后面紧跟着左括号的处理逻辑)
驱动出eval()中的操作符字符缓存逻辑。
####### 8.3.2.2.2.1.1 Add a Test
public void test_expr_with_pow()
{
Expression expr = new Expression("2**3");
assertEquals(8, expr.eval());
}####### 8.3.2.2.2.1.2 Write the Code 操作符后紧跟着数字。
public int eval()
{
StringBuffer digitBuffer = new StringBuffer();
StringBuffer operatorBuffer = new StringBuffer();
while(ctx.exprNotEnd())
{
char c = ctx.nextChar();
if('(' == c)
{
dsp.pushOperand(new Expression(ctx).eval());
}
else if(')' == c)
{
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
} //else digitBuffer.length() == 0 when right parenthesis followed by right parenthesis
return dsp.result();
}
else
{
if(isDigit(c))
{
if(operatorBuffer.length() != 0)
{
dsp.process(operatorBuffer.toString());
operatorBuffer = new StringBuffer();
} //else operatorBuffer.length() == 0 when operator followed by digit
digitBuffer.append(c);
}
else
{
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
digitBuffer = new StringBuffer();
} //else digitBuffer.length() == 0 when right parenthesis followed by an operator
operatorBuffer.append(c);
}
}
}
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
} //else digitBuffer.length() == 0 when expr ends with right parenthesis
return dsp.result();
}####### 8.3.2.2.2.1.3 Refactor the Code 无。
前面的"2**3"的测试用例虽然能测试通过，但会导致下面几个测试用例测试失败。
public void test_expr_with_right_parenthesis_followed_by_right_parenthesis()
{
Expression expr = new Expression("(48-(12+34))*10");
assertEquals(20, expr.eval()); //failed
Expression expr2 = new Expression("10*(48-(12+34))");
assertEquals(20, expr2.eval());
}
public void test_expr_with_nested_parentheses()
{
Expression expr = new Expression("((10+21)+34)*20");
assertEquals(1300, expr.eval());
Expression expr2 = new Expression("(50-(12+34))*20");
assertEquals(80, expr2.eval()); //failed
Expression expr3 = new Expression("((11+23)%11)*20");
assertEquals(20, expr3.eval());
Expression expr4 = new Expression("(12-(15-12))*10/(24-(12+10))/3");
assertEquals(15, expr4.eval());
Expression expr5 = new Expression("(100-(1920-1900))*2/(24-(12+10))/2");
assertEquals(40, expr5.eval());
}
public void test_expr_ends_with_right_parenthesis()
{
Expression expr = new Expression("10*(12+34)");
assertEquals(460, expr.eval()); //failed
}这几个失败的测试用例的共同点在于，操作符后面紧跟着左括号。借助于"2**(1+2)"测试用例，在eval()中增加操作符后面紧跟着左括号的处理逻辑。
####### 8.3.2.2.2.2.1 Add a Test
public void test_expr_with_operator_followed_by_left_parenthesis()
{
Expression expr = new Expression("2**(1+2)");
assertEquals(8, expr.eval());
}####### 8.3.2.2.2.2.2 Write the Code 操作符后面紧跟着左括号。
public int eval()
{
StringBuffer digitBuffer = new StringBuffer();
StringBuffer operatorBuffer = new StringBuffer();
while(ctx.exprNotEnd())
{
char c = ctx.nextChar();
if('(' == c)
{
if(operatorBuffer.length() != 0)
{
dsp.process(operatorBuffer.toString());
operatorBuffer = new StringBuffer();
} //else operatorBuffer.length() == 0 when operator followed by left parenthesis
dsp.pushOperand(new Expression(ctx).eval());
}
else if(')' == c)
{
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
} //else digitBuffer.length() == 0 when right parenthesis followed by right parenthesis
return dsp.result();
}
else
{
if(isDigit(c))
{
if(operatorBuffer.length() != 0)
{
dsp.process(operatorBuffer.toString());
operatorBuffer = new StringBuffer();
} //else operatorBuffer.length() == 0 when operator followed by digit
digitBuffer.append(c);
}
else
{
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
digitBuffer = new StringBuffer();
} //else digitBuffer.length() == 0 when right parenthesis followed by an operator
operatorBuffer.append(c);
}
}
}
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
} //else digitBuffer.length() == 0 when expr ends with right parenthesis
return dsp.result();
}####### 8.3.2.2.2.2.3 Refactor the Code eval()目前的实现存在几个代码的坏味道：代码比较长；操作数的缓存处理、操作符的缓存处理存在重复；代码偏实现、自述性不强等。
- 抽取processOperator()方法。
先打算将if('(' == c)分支中的operatorBuffer相关的代码抽取为processOperator()方法。
public int eval()
{
StringBuffer digitBuffer = new StringBuffer();
StringBuffer operatorBuffer = new StringBuffer();
while(ctx.exprNotEnd())
{
char c = ctx.nextChar();
if('(' == c)
{
//else operatorBuffer.length() == 0 when operator followed by left parenthesis
processOperator(operatorBuffer);
dsp.pushOperand(new Expression(ctx).eval());
}
else if(')' == c)
{
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
} //else digitBuffer.length() == 0 when right parenthesis followed by right parenthesis
return dsp.result();
}
else
{
if(isDigit(c))
{
if(operatorBuffer.length() != 0)
{
dsp.process(operatorBuffer.toString());
operatorBuffer = new StringBuffer();
} //else operatorBuffer.length() == 0 when operator followed by digit
digitBuffer.append(c);
}
else
{
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
digitBuffer = new StringBuffer();
} //else digitBuffer.length() == 0 when right parenthesis followed by an operator
operatorBuffer.append(c);
}
}
}
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
} //else digitBuffer.length() == 0 when expr ends with right parenthesis
return dsp.result();
}
private void processOperator(StringBuffer operatorBuffer)
{
if(operatorBuffer.length() != 0)
{
dsp.process(operatorBuffer.toString());
operatorBuffer = new StringBuffer();
}
}本以为这样的重构不会有问题，结果却发现下面的测试用例测试不通过了。
public void test_expr_with_nested_parentheses()
{
Expression expr = new Expression("((10+21)+34)*20");
assertEquals(1300, expr.eval());
Expression expr2 = new Expression("(50-(12+34))*20");
assertEquals(80, expr2.eval());
Expression expr3 = new Expression("((11+23)%11)*20");
assertEquals(20, expr3.eval());
Expression expr4 = new Expression("(12-(15-12))*10/(24-(12+10))/3");
assertEquals(15, expr4.eval()); //failed
Expression expr5 = new Expression("(100-(1920-1900))*2/(24-(12+10))/2");
assertEquals(40, expr5.eval());
}分析JUnit的提示信息，增加打印语句，发现出现了“//”操作符，感觉像是operatorBuffer没有清理干净导致的问题。
仔细查看抽取的processOperator()方法，既然怀疑是operatorBuffer没有清理干净导致的问题，自然会将焦点放在“operatorBuffer = new StringBuffer();”这条语句。这条语句想做的事情是清理以方法参数传入的operatorBuffer，而做事的方式是new了一个新的StringBuffer对象并赋值给名为operatorBuffer的变量。
private void processOperator(StringBuffer operatorBuffer)
{
if(operatorBuffer.length() != 0)
{
dsp.process(operatorBuffer.toString());
operatorBuffer = new StringBuffer();
}
}事实上，问题就出在这里。
因为抽取了processOperator()方法，在方法外面创建的operatorBuffer对象传入方法时，实际是把operatorBuffer对象的引用赋值给了processOperator()方法的形参operatorBuffer变量。需要注意的是，形参的operatorBuffer变量跟传入方法的operatorBuffer对象虽然名字一样，但其实是完全不同的。为了讲述方便，将形参变量重新命名为operatorBuffer'。operatorBuffer和operatorBuffer'两个变量指向了同一个内存地址。如下图所示：
“new了一个新的StringBuffer对象并赋值给名为operatorBuffer的变量”这个操作修改的是operatorBuffer'变量，而operatorBuffer变量并未受到任何影响。如下图所示。所以出现了operatorBuffer没有清理干净的问题。
如果不抽取processOperator()方法，不存在方法形参和实参绑定过程中的赋值过程，“new了一个新的StringBuffer对象并赋值名为operatorBuffer的变量”这个操作修改的就是operatorBuffer变量本身，所以程序运行没有问题。
processOperator()方法修改如下：
private void processOperator(StringBuffer operatorBuffer)
{
if(operatorBuffer.length() != 0)
{
dsp.process(operatorBuffer.toString());
operatorBuffer.delete(0, operatorBuffer.length());
}
}operatorBuffer和operatorBuffer’对象的引用情况，如下图所示：
delete操作修改的是两个对象引用共同指向的内存。operatorBuffer就能被清理干净了。
事实上，这么修改之后，之前测试不通过的测试用例就测试通过了。
- 用processOperator()方法替换eval()中operatorBuffer相关的代码。
public int eval()
{
StringBuffer digitBuffer = new StringBuffer();
StringBuffer operatorBuffer = new StringBuffer();
while(ctx.exprNotEnd())
{
char c = ctx.nextChar();
if('(' == c)
{
//else operatorBuffer.length() == 0 when operator followed by left parenthesis
processOperator(operatorBuffer);
dsp.pushOperand(new Expression(ctx).eval());
}
else if(')' == c)
{
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
} //else digitBuffer.length() == 0 when right parenthesis followed by right parenthesis
return dsp.result();
}
else
{
if(isDigit(c))
{
//else operatorBuffer.length() == 0 when operator followed by digit
processOperator(operatorBuffer);
digitBuffer.append(c);
}
else
{
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
digitBuffer = new StringBuffer();
} //else digitBuffer.length() == 0 when right parenthesis followed by an operator
operatorBuffer.append(c);
}
}
}
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
} //else digitBuffer.length() == 0 when expr ends with right parenthesis
return dsp.result();
}- 抽取processOperand()方法。需注意：
- 清理digitBuffer的方法改为delete。
- 重构前的代码中，有些digitBuffer相关的代码是不需要delete操作的，这里为了可以抽取统一的方法，统一加上了delete操作，不影响逻辑。
public int eval()
{
StringBuffer digitBuffer = new StringBuffer();
StringBuffer operatorBuffer = new StringBuffer();
while(ctx.exprNotEnd())
{
char c = ctx.nextChar();
if('(' == c)
{
//else operatorBuffer.length() == 0 when operator followed by left parenthesis
processOperator(operatorBuffer);
dsp.pushOperand(new Expression(ctx).eval());
}
else if(')' == c)
{
//else digitBuffer.length() == 0 when right parenthesis followed by right parenthesis
processOperand(digitBuffer);
return dsp.result();
}
else
{
if(isDigit(c))
{
//else operatorBuffer.length() == 0 when operator followed by digit
processOperator(operatorBuffer);
digitBuffer.append(c);
}
else
{
//else digitBuffer.length() == 0 when right parenthesis followed by an operator
processOperand(digitBuffer);
operatorBuffer.append(c);
}
}
}
//else digitBuffer.length() == 0 when expr ends with right parenthesis
processOperand(digitBuffer);
return dsp.result();
}
private void processOperand(StringBuffer digitBuffer)
{
if(digitBuffer.length() != 0)
{
dsp.process(digitBuffer.toString());
digitBuffer.delete(0, digitBuffer.length());
}
}- processOperator和processOperand()方法有重复，重构去重。
private void processOperand(StringBuffer digitBuffer)
{
processOperElement(digitBuffer);
}
private void processOperator(StringBuffer operatorBuffer)
{
processOperElement(operatorBuffer);
}
private void processOperElement(StringBuffer buffer)
{
if(buffer.length() != 0)
{
dsp.process(buffer.toString());
buffer.delete(0, buffer.length());
}
}表达式支持负整数。
代码包路径：fayelab.tdd.arithmetic.doublestack.negint
由Expression完成负数的解析。负号的判断方法是，首先它是一个“-”，其次，“-”是表达式的开头或者“-”前面是左括号。
因为操作数要支持负号，DoubleStackProcessor类中的allDigits()方法需要修改。
先后分别修改DoubleStackProcessor和Expression的测试代码和产品代码。
操作数支持负号。
测试用例如下：
19. -10 (操作数支持负号)
操作数支持负号。
public void test_negative_num()
{
dsp.process("-10");
assertEquals(asList(-10), dsp.dumpOperandStack());
assertEquals(asList(), dsp.dumpOperatorStack());
}allDigits()方法命名不再合适，改为isInteger()。
public void process(String item)
{
if(isInteger(item))
{
processOperand(item);
}
else
{
processOperator(item);
}
}
private boolean isInteger(String str)
{
return Pattern.matches("-?+\\d+", str);
}无。
完成负数的解析。负号的判断方法是，首先它是一个“-”，其次，“-”是表达式的开头或者“-”前面是左括号。
测试用例如下：
9. "-12" (eval()中增加表达式以负号开头的处理逻辑)
10. "(-12)" (eval()中增加负号前面是左括号的处理逻辑)
eval()中增加表达式以负号开头的处理逻辑。
public void test_expr_with_minus_when_expr_starts_with_minus()
{
Expression expr = new Expression("-12");
assertEquals(-12, expr.eval());
}Expression Class
public int eval()
{
StringBuffer digitBuffer = new StringBuffer();
StringBuffer operatorBuffer = new StringBuffer();
while(ctx.exprNotEnd())
{
char c = ctx.nextChar();
if('(' == c)
{
//else operatorBuffer.length() == 0 when operator followed by left parenthesis
processOperator(operatorBuffer);
dsp.pushOperand(new Expression(ctx).eval());
}
else if(')' == c)
{
//else digitBuffer.length() == 0 when right parenthesis followed by right parenthesis
processOperand(digitBuffer);
return dsp.result();
}
else
{
if(isDigit(c))
{
//else operatorBuffer.length() == 0 when operator followed by digit
processOperator(operatorBuffer);
digitBuffer.append(c);
}
else if(isMinusLeadingExpr(c))
{
digitBuffer.append(c);
}
else
{
//else digitBuffer.length() == 0 when right parenthesis followed by an operator
processOperand(digitBuffer);
operatorBuffer.append(c);
}
}
}
//else digitBuffer.length() == 0 when expr ends with right parenthesis
processOperand(digitBuffer);
return dsp.result();
}
private boolean isMinusLeadingExpr(char c)
{
return c == '-' && ctx.isCurCharLeadingExpr();
}Context Class
boolean isCurCharLeadingExpr()
{
return curIdx == 1;
}无。
eval()中增加负号前面是左括号的处理逻辑。
public void test_expr_with_minus_when_negative_num_wrapped_with_parentheses()
{
Expression expr = new Expression("(-12)");
assertEquals(-12, expr.eval());
}Expression Class
private boolean isMinusLeadingExpr(char c)
{
return c == '-' && (ctx.isCurCharLeadingExpr() || '(' == ctx.prevChar());
}Context Class
public char prevChar()
{
return expr.charAt(curIdx - 2);
}无。
至此支持负整数的代码已全部实现。这里只是用一些复杂的测试用例验证一下。
public void test_expr_with_minus()
{
Expression expr = new Expression("((12))");
assertEquals(12, expr.eval());
Expression expr2 = new Expression("-10+20");
assertEquals(10, expr2.eval());
Expression expr3 = new Expression("(-10)+20");
assertEquals(10, expr3.eval());
Expression expr4 = new Expression("20+(-10)");
assertEquals(10, expr4.eval());
Expression expr5 = new Expression("(-11+12)*1-15+12/2");
assertEquals(-8, expr5.eval());
Expression expr6 = new Expression("(11+12)*(-1)-(15+12/2)");
assertEquals(-44, expr6.eval());
Expression expr7 = new Expression("((12+(-11))*2-11)*3");
assertEquals(-27, expr7.eval());
}在支持了多位正整数、幂操作符和负整数以后，Expression类的eval()方法变得有些难以理解，表达式解析逻辑和递归逻辑混在了一起。
新定义一个Parser类专门负责表达式解析。把Expression类的eval()方法中的解析逻辑挪到Parser类中。Context类的解析逻辑，如exprNotEnd ()、nextChar()等方法，也挪到Parser类中。
Context类变成一个纯数据类。Parser类负责解析。Expression类包含Context、DoubleStackProcessor和Parser成员变量，它的eval()方法中主要是递归逻辑。也就是说每一个表达式/子表达式都拥有自己的DoubleStackProcessor和Parser。
代码包路径：fayelab.tdd.arithmetic.doublestack.parser
在DoubleStackProcessor类已经支持多位正整数、多位操作符和负整数的前提下，重写Expression类。
测试用例如下：
1. "12" (驱动出Expression/Parser/Context主体代码和处理多位数的逻辑)
2. "10**2" (驱动出处理多位操作符的逻辑)
3. "-12" (驱动出处理负号的逻辑)
4. "10*(48-(12+34))" (驱动出处理括号但不含负号的逻辑，主要是递归逻辑)
5. "((12+(-11))*2-11)**2" (驱动出处理括号且含负号的逻辑)
驱动出Expression/Parser/Context主体代码和处理多位数的逻辑。
ExpressionTest.java
import junit.framework.TestCase;
public class ExpressionTest extends TestCase
{
public void test_multidigit_operand()
{
Expression expr = new Expression("12");
assertEquals(12, expr.eval());
}
}Expression.java Expression Class
public class Expression
{
private Context ctx;
private DoubleStackProcessor dsp;
private Parser parser;
public Expression(String expr)
{
this(new Context(expr, 0));
}
Expression(Context ctx)
{
this.ctx = ctx;
this.dsp = new DoubleStackProcessor();
this.parser = new Parser(ctx);
}
public int eval()
{
while(parser.exprNotEnd())
{
String item = parser.nextItem();
dsp.process(item);
}
return dsp.result();
}
}Expression.java Parser Class
class Parser
{
private Context ctx;
Parser(Context ctx)
{
this.ctx = ctx;
}
boolean exprNotEnd()
{
return ctx.curIdx < ctx.expr.length();
}
String nextItem()
{
char c = nextChar();
return c + subsequence(c);
}
private char nextChar()
{
char c = ctx.expr.charAt(ctx.curIdx);
ctx.curIdx += 1;
return c;
}
private String subsequence(char c)
{
return nextOperand();
}
private String nextOperand()
{
String result = "";
while(isDigit(peekChar()))
{
result += nextChar();
}
return result;
}
private char peekChar()
{
return exprNotEnd() ? ctx.expr.charAt(ctx.curIdx) : Character.MIN_VALUE;
}
private boolean isDigit(char c)
{
return '0' <= c && c <= '9';
}
}Expression.java Context Class
class Context
{
String expr;
int curIdx;
Context(String expr, int curIdx)
{
this.expr = expr;
this.curIdx = curIdx;
}
}无。
驱动出处理多位操作符的逻辑。
ExpressionTest.java
public void test_multichar_operator()
{
Expression expr = new Expression("10**2");
assertEquals(100, expr.eval());
}Expression.java Parser Class
private String subsequence(char c)
{
if(isDigit(c))
{
return nextOperand();
}
if(isOpChar(c))
{
return nextOperator();
}
return "";
}
private String nextOperator()
{
String result = "";
while(isOpChar(peekChar()))
{
result += nextChar();
}
return result;
}
private boolean isOpChar(char c)
{
return "+-*/%".indexOf(c) > -1;
}无。
驱动出处理负号的逻辑。
ExpressionTest.java
public void test_negative_operand()
{
Expression expr = new Expression("-12");
assertEquals(-12, expr.eval());
}Expression.java Parser Class
private String subsequence(char c)
{
if(isDigit(c))
{
return nextOperand();
}
if(isNegative(c))
{
return nextOperand();
}
if(isOpChar(c))
{
return nextOperator();
}
return "";
}
private boolean isNegative(char c)
{
return c == '-' && ctx.curIdx == 1;
}- 减号在表达式开头是负号。
- 在subsequence()方法中，isNegative(c)判断分支要放在isOpChar(c)判断分支之前，否则会被先判断为减号操作符。
1 Parser类中的nextOperand()方法和nextOperator()方法存在重复代码，抽取nextItem(Predicate pred)方法。
Expression.java Parser Class
import java.util.function.Predicate;
private String nextOperand()
{
return nextItem(this::isDigit);
}
private String nextOperator()
{
return nextItem(this::isOpChar);
}
private String nextItem(Predicate<Character> pred)
{
String result = "";
while(pred.test(peekChar()))
{
result += nextChar();
}
return result;
}2 优化subsequence()方法的分支逻辑。
Expression.java Parser Class
private String subsequence(char c)
{
if(isDigit(c) || isNegative(c))
{
return nextOperand();
}
if(isOpChar(c))
{
return nextOperator();
}
return "";
}驱动出处理括号但不含负号的逻辑，主要是递归逻辑。
ExpressionTest.java
public void test_parenthesis_without_negative()
{
Expression expr = new Expression("10*(48-(12+34))");
assertEquals(20, expr.eval());
}Expression.java Expression Class
public int eval()
{
while(parser.exprNotEnd())
{
String item = parser.nextItem();
if("(".equals(item))
{
dsp.pushOperand(new Expression(ctx).eval());
}
else if(")".equals(item))
{
return dsp.result();
}
else
{
dsp.process(item);
}
}
return dsp.result();
}无。
驱动出处理括号且含负号的逻辑。
ExpressionTest.java
public void test_parenthesis_with_negative()
{
Expression expr = new Expression("((12+(-11))*2-11)**2");
assertEquals(81, expr.eval());
}Expression.java Parser Class
private char prevChar()
{
return ctx.expr.charAt(ctx.curIdx - 2);
}
private boolean isNegative(char c)
{
return c == '-' && (ctx.curIdx == 1 || prevChar() == '(');
}isNegative()方法增加减号前面是“(”的判断分支，这种情况下减号是负号。
无。