专栏首页xiaoxi666的专栏状态机编程思想(1):括号内外字符串统计

状态机编程思想(1):括号内外字符串统计

这是曾经的一个面试题,正好引出状态机编程思想。挺不错的一个例子。

题目描述

给定一个字符串,它由以下字符组成:

  • 左括号“(”
  • 右括号“)”
  • 下划线“_” 
  • 大小写字母构成的字符串(单字母也算作字符串)

该字符串组成有以下规则限定:

  • 括号成对出现且不会嵌套,保证语法正确
  • 字符串可以出现在括号内,也可以出现在括号外
  • 各个字符串之间必须用下划线“_”隔开
  • 括号外的字符串必须以下划线“_”为边界;括号内字符串的边界可以是下划线“_”,也可以是括号“(”、“)”

请解决问题:

  • 括号内字符串个数
  • 统计括号外最长字符串的长度

 传统思路

我们拿到这个问题时,第一感觉往往是顺序遍历字符串,并检测左右相邻字符是否满足边界条件,从而进行分支处理。但是这样做有以下棘手之处:

  • 判定括号边界时需要保存之前的状态,而处理程序和判定状态逻辑往往混乱成一锅粥,难解难分
  • 不同状态下的处理逻辑不同,这样对于大型问题,逻辑之间有可能产生耦合,甚至在不同状态间跳来跳去
  • 还有效率问题,每次处理当前字符时还有同时处理左右相邻字符,工作量有冗余,效率降低

嗯,不信的话,可以自己按照上述最简单的思路实现一下,你就明白了。

有人说,复杂逻辑我不怕啊,细心就好。So...是时候请出我们的大侠--“状态机”了。

状态机思路

状态机是编译原理中的一种技术,学过电学的读者应该也在《数字电子技术》中用过它,归根结底,就是把复杂的问题逻辑化为一个一个的状态,我们处理问题的过程就是在各个状态之间不断迁移(包含自迁移),这样画出来的图就叫做状态迁移图,帮助我们把一锅难缠的粥转化为一张清晰的网。当然,这里不会深究状态机的概念,详情请自查(比如还有状态迁移表等等)。

让我们用状态迁移图表示上面的问题(若看不清图,可以右键在新的标签页看,或者下载下来看):

我设置了两个状态,一个用来区分括号内外,一个用来区分是否是字母,从而进行不同的处理。

括号内外分成了两个子状态,这两个子状态是互斥的,因此他们内部的状态变量可以共用。

至于状态之间转移条件,直接看代码即可理解:

 1 public class CountWords {
 2 
 3     final static int InBracket = 0;// 括号内
 4     final static int OutBracket = 1;// 括号外
 5 
 6     final static int IsLetter = 0;// 是字母
 7     final static int NotLetter = 1;// 不是字母
 8 
 9     public static void main(String[] args) {
10         test("_yy_()()_(_apple_welcome)_ssjjjs_");//2,6
11         test("__()()_(_)__()_");//0,0
12         test("_ya_");//0,2
13         test("_yy_(_)(r)_(_wel_c_ome_k)_");//5,2
14         test("_yy_aa_");//0,2
15         test("_yy_(aaa_bb_c)()__yyyyy_");//3,5
16         test("(u)_()_(__)()_yy_()");//1,2
17         test("__(a_wwwww)");//2,0
18         test("__(_a_wwwww_)_____ddd____()()()()()()");//2,3
19     }
20 
21     public static void test(String str) {
22         // 状态初始化
23         int state_INOUT = OutBracket;
24         int state_letter = NotLetter;
25         // 统计结果初始化
26         int outLengthOfLongestWord = 0;
27         int outLengthOfCurrentWord = 0;
28         int inNumsOfWord = 0;
29         // 开始处理
30         for (int i = 0; i < str.length(); ++i) {
31             // 取出当前字符
32             char c = str.charAt(i);
33             // 根据括号设置状态:括号内、括号外
34             if (c == '(') {
35                 state_INOUT = InBracket;
36             }
37             if (c == ')') {
38                 state_INOUT = OutBracket;
39             }
40             // 括号内状态
41             if (state_INOUT == InBracket) {
42                 if (state_letter == IsLetter) {
43                     if (c == '_' || c == ')') {
44                         state_letter = NotLetter;
45                     }
46                 } else if (state_letter == NotLetter) {
47                     if (Character.isLetter(c)) {
48                         state_letter = IsLetter;
49                         ++inNumsOfWord;
50                     }
51                 }
52             }
53             // 括号外状态
54             else if (state_INOUT == OutBracket) {
55                 if (state_letter == IsLetter) {
56                     // System.out.println(c);
57                     if (c == '_' || c == '(') {
58                         if (outLengthOfLongestWord < outLengthOfCurrentWord) {
59                             outLengthOfLongestWord = outLengthOfCurrentWord;
60                         }
61                         outLengthOfCurrentWord = 0;
62                         state_letter = NotLetter;
63                     } else if (Character.isLetter(c)) {
64                         ++outLengthOfCurrentWord;
65                     }
66                 }
67                 if (state_letter == NotLetter) {
68                     if (Character.isLetter(c)) {
69                         state_letter = IsLetter;
70                         ++outLengthOfCurrentWord;
71                     }
72                 }
73             }
74         }
75         System.out.println("括号内的字符串数:" + inNumsOfWord);
76         System.out.println("括号外的最长字符串长度:" + outLengthOfLongestWord);
77         System.out.println();
78 
79     }
80 
81 }

有没有感觉到很方便?思路更清晰了,效率也上去了。

注:状态机不同于设计模式中常说的状态模式(状态模式用类代表状态)。

就这么多吧,欢迎提出测试样例找bug,共同进步。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【左神算法课】子数组最大差值小于某阈值,求满足条件的子数组个数

      1.从第一个元素开始依次向后遍历,同时维护两个窗口(由于要同时操作窗口的头部和尾部,故采用双端队列):

    xiaoxi666
  • 最长滑道问题(非递归,C++)

    题目描述请参考博客http://blog.csdn.net/sinat_30186009/article/details/52356053,在此表示感谢。

    xiaoxi666
  • 【模板小程序】获得一段区间内的随机数

    注意,由于rand()直接产生的数据范围很大(0~RAND_MAX),其中RAND_MAX在VS2010下为0x7fff,也就是32767。因此要获取的数据量较...

    xiaoxi666
  • HDU 1005 Number Sequence【多解,暴力打表,鸽巢原理】

    Number Sequence Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32...

    Angel_Kitty
  • python爬虫笔记之re.compile.findall()

    re.compile.findall原理是理解了,但输出不大理解(主要是加了正则表达式的括号分组) 

    逆向小白
  • FutureTask 原理

    如上代码主线程会在futureTask.get()出阻塞直到task任务执行完毕,并且会返回结果。

    加多
  • 【WordPress优化二】去掉不必要的东西

    主题选好了还没有完,因为WordPress系统自身还拥有一些优化的空间,因此我们可以对WordPress进行一些适量的优化。

    夏末浅笑
  • AutoAssign: Differentiable Label Assignment for Dense Object Detection

    绝命生
  • 《Bash 脚本教程》发布了

    Bash 是 Linux 和 Mac 的默认 Shell(命令行环境),系统管理和服务器开发都需要它。虽然不难,但是语法很怪异,比如计算字符串的长度要写成${#...

    ruanyf
  • 【专知荟萃22】机器阅读理解RC知识资料全集(入门/进阶/论文/综述/代码/专家,附查看)

    机器阅读理解(Reading Comprehension)专知荟萃 入门学习 进阶论文 综述 Datasets Code 领域专家 入门学习 深度学习解决机器阅...

    WZEARW

扫码关注云+社区

领取腾讯云代金券