TDD Kata 之括号配对

TDD · asj · 于 发布 · 最后由 topgao回复 · 809 次阅读
377

新年将至,微信里满屏都是年会和中奖,透露着越来越近的节日气氛。
小波同学在TDD群里抛出了一道题。

来抛个题,想了一晚上没做出来

题目是Balanced Parentheses,英文描述就不贴了。说起来挺简单,

一个字符串,判断它里面的括号是否配对
比如:
(5+6)∗(7+8)/(4+3)
是配对的,而
:-)
())(
则不是

顺便一提,在cyber-dojo.org上有这道题,而且是升级版。

不知道是不是因为每个程序员或多或少都有过人肉数括号的烦恼,还是小波声称的一晚上没做出来带来的激励效果。一下在群里引发了热议。
就在周师傅还在遗憾手边没电脑,正琢磨着是不是要手机上TDD的时候。鄢倩已经贴出了第一份代码
鄢倩 Clojure

紧随其后的是没有尾巴
没有尾巴跑得快 Scala

申导两连发
申导 人生苦短,我用Python可以写两遍

代码好多,美中不足的是只有结果,没看到产生的过程。周师傅终于拿到电脑贴出了TDD记录:
http://cyber-dojo.org/kata/edit/6320CF1239?avatar=hippo
顺便给还没机会用上函数式语言的同学带来些许安慰。

public class BalancedParentheses {
    public boolean valid(String exp) {
        return valid(exp, 0);
    }

    private boolean valid(String exp, int balance) {
        if (exp.isEmpty())
            return isBalanced(balance);
        if (isLeftParentheses(headChar(exp)))
            return valid(tailOf(exp), balance + 1);
        if (isRightParentheses(headChar(exp)) && isBalanced(balance))
            return false;
        if (isRightParentheses(headChar(exp)))
            return valid(tailOf(exp), balance - 1);
        return valid(tailOf(exp), balance);    
    }

    private boolean isLeftParentheses(char c) {
        return c == '(';
    }

    private boolean isRightParentheses(char c) {
        return c == ')';
    }

    private boolean isBalanced(int balance) {
        return balance == 0;
    }

    private char headChar(String exp) {
        return exp.charAt(0);
    }

    private String tailOf(String exp) {
        return exp.substring(1);
    }
}

回答太过热烈,没有尾巴同学忍不住提高难度,挑战升级版。

如何修改代码能够同时支持 和{}
要考虑这样的用例 [(])

但是这样的程度显然不够看,瞬间被秒
还是Python

还是Clojure

一直在围观,似乎对+1 -1非常在意的麦宇安老师。终于出手了。弄出了一个没有加减一,又不压栈的版本,说是什么用函数组合来代替栈或者计数。
具体来说就是……
好吧,算了还是自己看吧。
麦宇安 F#


更新的分割线
大概是函数组合过于华丽,周师傅忍不住按照这个思路做了一遍,而且是用没有函数式特性的JAVA。

public class BalancedParentheses {
    public boolean matchBalancedParentheses(String exp) {
        if (hasLeftParentheses(exp))
            return matchRightParentheses(afterLeftParentheses(exp)); 
        if (hasRightParentheses(exp))
            return false;
        return true;
    }

    private boolean matchRightParentheses(String exp) {
        if (hasLeftParentheses(exp))
            return matchBalancedParentheses(exp) &&
                   matchRightParentheses(afterRightParentheses(exp));
        if (hasRightParentheses(exp))
            return true;
        return false;
    }

    private String afterLeftParentheses(String exp) {
        return exp.substring(exp.indexOf('(')+1);
    }

    private String afterRightParentheses(String exp) {
        return exp.substring(exp.indexOf(')')+1);
    }

    private boolean hasLeftParentheses(String exp) {
        return exp.indexOf('(') >= 0;
    }

    private boolean hasRightParentheses(String exp) {
        return exp.indexOf(')') >= 0;
    }
}

看起来很像吧,然而其实有着本质的不同。
而且,随后申导发现了一个失败的测试用例。
"I told him (that not (yet)done).(but he)"
经过一长串的修改后,JAVA版函数式终于闪亮登场

import java.util.function.Predicate;

public class BalancedParentheses {
    public boolean matchBalancedParentheses(String exp) {
        if (hasLeftParentheses(exp))
            return matchRightParentheses(afterLeftParentheses(exp), 
                   nextExp -> matchBalancedParentheses(nextExp));
        if (hasRightParentheses(exp))
            return false;
        return true;
    }

    private boolean matchRightParentheses(String exp, Predicate<String> nextStep) {
        if (hasLeftParentheses(exp))
            return matchRightParentheses(afterLeftParentheses(exp), 
                   nextExp -> matchRightParentheses(nextExp, nextStep));
        if (hasRightParentheses(exp))
            return nextStep.test(afterRightParentheses(exp));        
        return false;
    }

    private String afterLeftParentheses(String exp) {
        return exp.substring(exp.indexOf('(')+1);
    }

    private String afterRightParentheses(String exp) {
        return exp.substring(exp.indexOf(')')+1);
    }

    private boolean hasLeftParentheses(String exp) {
        return exp.indexOf('(') >= 0 && (exp.indexOf(')') == -1 || 
               exp.indexOf('(') < exp.indexOf(')'));
    }

    private boolean hasRightParentheses(String exp) {
        return exp.indexOf(')') >= 0;
    }
}

http://cyber-dojo.org/kata/edit/677B72062C?avatar=crab

最后是我的作弊解法。话说用语言自带的库作弊,也算作弊么? [汗]……

import scala.util.parsing.combinator.RegexParsers

class ParenthesesParser extends RegexParsers {
  def part: Parser[Any] = "[^()]+".r
  def factor: Parser[Any] = part | "("~expr~")"
  def expr: Parser[Any] = rep(factor)
}

  //Test
  "expr" should "accept parentheses in row" in {
    parser.parseAll(parser.expr, "").successful shouldBe true
    parser.parseAll(parser.expr, "(abc)(12)").successful shouldBe true
    parser.parseAll(parser.expr, "(abc)12)").successful shouldBe false
    parser.parseAll(parser.expr, "(abc(123)*(12))").successful shouldBe true
    parser.parseAll(parser.expr, "I told him (that not (yet)done).(but he)").successful shouldBe true
  }

如果你也是这么一个习惯解题,磨练编程技巧,对TDD充满好奇或是热情的程序员。
快到群里来吧。


「软件匠艺社区」旨在传播匠艺精神,通过分享好的「工作方式」和「习惯」以帮助程序员更加快乐高效地编程。
本帖已被设为精华帖!
共收到 5 条回复
1
hkliya · #1 ·

谢谢分享!我正在做一个头条模块,这样直接贴文章地址就可以了。

377
asj · #2 ·

#1楼 @hkliya 头条怎么玩,我还没玩过呢

1
hkliya · #3 ·

#2楼 @asj 就贴地址和标题就可以了,参考 toutiao.io

1
hkliya · #4 ·

研究了一下,用 >引用一段原文,再贴个地址就可以了。

效果如下图:

96
topgao · #5 ·

加大难度加大难度!除了大中小三种括号,输入也要改成流(大到内存装不下)

需要 登录 后回复方可回复, 如果你还没有账号你可以 注册 一个帐号。