状态机编程思想(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 条评论
登录 后参与评论

相关文章

来自专栏Java后端技术栈

Java大型互联网公司经典面试题,论JDK源码的重要性的无限思考

论JDK源码的重要性:一道面试题引发的无限思考!大家在看到这个标题时想的是什么?小编我为什么要讲这个问题呢?

14610
来自专栏xingoo, 一个梦想做发明家的程序员

const指南

基本词义  意思就就是说利用const进行修饰的变量的值在程序的任意位置将不能再被修改,就如同常数一样使用!  使用方法 const int a=1;//这里定...

204100
来自专栏互联网技术栈

《Effective Java 》系列一

编写实例受控类有几个原因。实例受控使得类可以确保他是一个Singleton或者是不可实例化的。他还使得不可变类可以确保不会存在两个相等的实例。

22840
来自专栏java学习

面试题63(链表,哈希表)

关于链表,哈希表 1·以下关于链式存储结构的叙述中哪一个是正确的? A.链式存储结构不是顺序存取结构 B.逻辑上相邻的节点物理上必须邻接 C.可以通过计算直接确...

31660
来自专栏码神联盟

java常见异常汇总

程序猿的成长之路,从这开始.......... ? 在6月的投票中,结果昨天已经出来了,大家多数的希望多推送一些java的基础知识。首先来一下热...

43360
来自专栏IT派

全面深入理解Python面向对象编程

面向过程编程最易被初学者接受,其往往用一长段代码来实现指定功能,开发过程中最常见的操作就是粘贴复制,即:将之前实现的代码块复制到现需功能处。

13420
来自专栏博客园

MSIL学习------从HelloWorld开始

  前段时间突然想搞搞IL语言,于是在博客园中找到了包建强前辈关于IL的文章学习,并且在包前辈博客里看到了09年他与赵劼前辈关于是否有必要学习IL语言的争论,作...

14830
来自专栏编程一生

PHP开发人员对JAVA的WEB开发入门(初版-基础知识)

13340
来自专栏玄魂工作室

Hacker基础之Linux篇:基础Linux命令六

以后这个系列的每次就浓缩一下只推送一个命令~ ? sort sort命令是帮我们依据不同的数据类型进行排序,在Linux里非常常用的一个命令 sort命令使用...

36460
来自专栏韩伟的专栏

框架设计原则和规范(三)

此文是《.NET:框架设计原则、规范》的读书笔记,本文内容较多,共分九章,将分4天进行推送,今天推送6-7章。 1. 什么是好的框架 2. 框架设计...

39460

扫码关注云+社区

领取腾讯云代金券