TC官方合作论坛

标题: 【有源码】栈的典型应用-带你探秘tc表达式括号匹配 [打印本页]

---

作者: rainshine    时间: 2014-1-12 14:52
标题: 【有源码】栈的典型应用-带你探秘tc表达式括号匹配
午后的阳光真暖和那，大家有木有在睡午觉呢。~~~
[attach]13863[/attach]哇哈哈好自豪好几篇都是我文章呢。啦啦。谢谢看官们的支持。rainshine会继续努力，写更多的实用函数，公开更多好的源码！！
今天带来的公开例程：
[attach]13864[/attach]

引言：rainshine不知道各位朋友在编程的时候有木有思考过一个问题——tc或者其他的开发环境，是怎么判断某个表达式的括号是不是匹配的呢？
例如这段代码：
    if(str.findstr(edit.gettext("edit0"),"test"))>0)
    endif

编译时会提示：
>错误:C:\Documents and Settings\Administrator\桌面\栈的应用\栈的应用\栈的应用.t 行号:12 错误信息:'if'语句的条件表达式错误'(str.findstr(edit.gettext("edit0"),"test"))>0)'
仔细观察就会发现，在"test"右边多了多了一个括号。
那么编译器是怎么实现的这个效果呢？

其实，表达式处理是 高级语言程序设计编译的一个基本问题。它的实现就是栈的典型应用。
检查if和endif，下标运算符是否匹配，计算多重表达式的值，函数的递归调用，这些都是栈的功劳。
（个人感觉tc的动态数组貌似是链表- -）那么，我们用tc该如何写这个功能呢？这时，tc的动态数组可就帮了我们大忙了。
我们不需要再懂得指针或者其他的乱七八糟的数据结构的知识，只需要掌握了数组空间的API命令就可以轻松模拟一个栈。

我们从简单的开始剖析，匹配圆括号的思路如下：
首先读入一个表达式，从左到右扫描每个字符，若是左括号就压进栈（存入数组）；若是右括号就让栈顶元素出栈，当栈溢出（数组为空，右括号找不到老婆(左括号)），或当表达式扫描完毕，而栈却非空（有女嘉宾(左括号)找不到中意的男嘉宾~）时，都返回不匹配。否则就返回匹配。

算法描述如下：
定义数组
s←读入表达式
len←字符串长度
top←栈顶指针赋值-1
  从0开始遍历到len
    如果 获得字符是左括号：
      top←top+1
      数组增加一个元素
    如果结束
    如果 获得字符是右括号：
      若栈顶指针为-1则 直接跳出并返回不匹配  //即：帅哥找不到美女
      top←top-1
    如果结束
  遍历结束
如果 栈顶指针为-1：//即：有剩余美女没有找到帅哥
返回不匹配
否则 返回匹配
如果结束
以上就是匹配小括号（圆括号）的过程，有人可能会说，我靠！这么麻烦！直接遍历字符串然后一个变量记录多少个左括号，一个变量记录多少个右括号，遍历完后看这俩变量数值一不一样不就成了。不急，请继续往下看。

其实，真正写程序时，表达式中通常会有中括号（数组下标运算）或者大括号、尖括号等，难道我们要定义多个栈，判断是什么类型的括号就进哪个栈吗？？
答案是，不需要！no！哈、拽个英文。
那么，该如何实现   <[8*8]>   返回匹配    <[(9*9]>  返回不匹配呢？
咳咳，确实，定义变量记录有多少个左右括号，然后看是否相等，这样可以实现，
但——    [(9*9])   这样的表达式，打眼一看明显不匹配，左右括号嵌套错误，可左右括号数相等，用那种方法就明显行不通了。
这时候，NB的栈就闪亮登场啦！


百度了一下括号匹配算法，随便看了两三篇文章，发现都是用switch语句实现的 先确定括号类型再判断是否匹配，
我觉得可以不用这样，我们定义一个数组，非别存放每个括号的ascii码：
    c[0]=str.strgetat("{",0)
    c[1]=str.strgetat("(",0)
    c[2]=str.strgetat("[",0)
    c[3]=str.strgetat("<",0)
    c[4]=str.strgetat(">",0)
    c[5]=str.strgetat("]",0)
    c[6]=str.strgetat(")",0)
    c[7]=str.strgetat("}",0)

定义一个函数，遇到左括号时，返回数组下标（0-3）；把下标压入栈；
遇到右括号时，也获取数组下标（4-7），把这个下标值与栈顶元素存储的下标值相加，如果为7那么就是匹配，否则就是不匹配。
即：第二个（左括号）和第五个（右括号）：2+5=7匹配，第一个和第六个：1+6=7匹配，第三个和第五个：3+5=8不匹配……
如此这般就可以很简单地实现，将 [(9*9])  这样的表达式识别为不匹配，因为明显1+5不等于7！


总体思路如下：
从字符串中读入一个左括号时，就将其压入栈；当读入一个有括号时，就从栈顶取出左括号与其检查、比较，若匹配就将左括号出栈 并继续读字符，否则直接返回不匹配。全部的字符读完之后，检查栈是否为空，若不为空（左括号有剩余）则显示不匹配，否则就是匹配啦~~吼吼！终于说完了。这么长——————————————————————


好了，现在是开源时间！累屎了。这篇文章打字打了一个小时，希望大家给个有意义的回复或者评分，支持我继续做免费开源的共享~~谢谢。。

---

作者: 君笨笨    时间: 2014-1-12 14:57
大神，我来了~~~~~~~

---

作者: zxw445    时间: 2014-1-12 14:58
- -，好厉害的大神，佩服佩服。。。。。求大神教我。。。。

---

作者: 美珍子    时间: 2014-1-12 14:59
你整天泡在这里。你想当官了。

---

作者: rainshine    时间: 2014-1-12 15:15

美珍子 发表于 2014-1-12 14:59
你整天泡在这里。你想当官了。

没啊 要不我也闲着没事 而且、、、我乐于助人！！！

---

作者: rainshine    时间: 2014-1-12 15:15

zxw445 发表于 2014-1-12 14:58
- -，好厉害的大神，佩服佩服。。。。。求大神教我。。。。

。。。。

---

作者: qisi2012    时间: 2014-1-12 15:22
顶上。。感谢分享

---

作者: as128214121    时间: 2014-1-12 15:27
好，

---

作者: 美珍子    时间: 2014-1-12 15:29


你弄一个功能集。这样就更方便了。

---

作者: rainshine    时间: 2014-1-12 15:33

美珍子 发表于 2014-1-12 15:29
你弄一个功能集。这样就更方便了。

你咋知道的 我已经弄了，只不过还没公开。

---

作者: zxw445    时间: 2014-1-12 15:35

rainshine 发表于 2014-1-12 15:33
你咋知道的 我已经弄了，只不过还没公开。

期待大神的发展，我会一路支持到底的。

---

作者: 1757663220    时间: 2014-1-12 19:43
try讨厌讨厌

---

作者: 菜鸟狙丶    时间: 2014-1-12 21:26
很棒啊

---

作者: rainshine    时间: 2014-1-15 23:02
呜呜呜 没人顶了！这篇帖子如此之精品嘿嘿！新手看不懂难道大神也不懂555~~我自己顶

---

作者: chenxi2013    时间: 2014-1-31 02:16
看看呢

---

作者: rainshine    时间: 2014-1-31 10:03

chenxi2013 发表于 2014-1-31 02:16
看看呢

居然还有人来看这个贴！！本来以为绝对沉了。

---

作者: awlbm    时间: 2014-3-1 08:12
共享~~谢谢

---

作者: rxuehao    时间: 2014-3-4 17:16
谢谢！！！

---

作者: 394345857    时间: 2014-4-18 23:58
来看了

---

作者: lx0113    时间: 2014-4-19 00:00
:smoke 泪流满面！原来这样的…

---

作者: yiye3376    时间: 2014-5-2 16:46
很给力，学到了不少，继续看隐

---

作者: blublu    时间: 2014-5-4 17:21
楼主幸苦了,谢谢分享!!

---

作者: lukeigun    时间: 2014-5-15 00:49
谢谢分享！！！

---

作者: 366760348    时间: 2014-5-15 23:50
学习谢谢

---

作者: 续花丶    时间: 2014-5-16 19:27
学习一下。

---

作者: 67800461    时间: 2014-5-21 06:30
111111111111

---

作者: chinaxhb    时间: 2014-5-21 09:04
我要下载.

---

作者: a1648004555    时间: 2014-5-22 19:54
hhhhhhhhhhhhhhhhh

---

作者: 小豪    时间: 2014-6-10 00:49
那地方纷纷

---

作者: nxjclement    时间: 2014-6-21 01:24
快到碗里来111

---

作者: da1990    时间: 2014-8-16 19:05
感觉很精辟 小手一抖哦，经验就到手哦

---

作者: flm213    时间: 2014-8-21 14:38
不错学习

---

作者: 紫㈩龍    时间: 2014-9-8 19:56
学习下你们的脚本思路.

---

作者: rainshine    时间: 2014-9-8 19:59

紫㈩龍 发表于 2014-9-8 19:56
学习下你们的脚本思路.

谢谢支持!

---

作者: qianlanzf    时间: 2014-10-7 22:38
顶顶顶顶顶多大

---

作者: qq372997216    时间: 2014-11-5 23:50
3333333333333333333333

---

作者: T星人    时间: 2014-11-12 05:54


谢谢分享~~
好帖   
膜拜大神,  这么深奥内容 软件应用开发专业吗,   

---

作者: OOOO    时间: 2014-12-5 23:30
你咋知道的 我

---

作者: T星人    时间: 2014-12-14 12:11
楼主的逻辑思维能力很强啊，膜拜~~

---

作者: T星人    时间: 2014-12-14 12:16
栈的应用我是在编写10进制转换16进制的代码的时候自己领悟的，
”先进后出，后进先出“ 就是我印象中的堆栈，
用一维数组实现，具体物理地址是什么样俺就不清楚了

---

作者: jiangyutao1999    时间: 2014-12-16 20:59

---

作者: 360310304    时间: 2014-12-19 21:33
感谢楼主分享

---

作者: ycheng86106    时间: 2015-2-13 16:32
回复学习

---

作者: menglovelili    时间: 2015-3-18 12:53
学习学习

---

作者: psxly    时间: 2015-4-13 14:00
回帖是种美德

---

作者: lfju    时间: 2015-6-29 10:27
感谢分享

---

作者: oycs429    时间: 2015-9-17 11:48

---

作者: 153798846    时间: 2015-11-18 20:10
111111111111111111

---

作者: 740045982    时间: 2015-12-17 00:57

---

作者: wang220211    时间: 2016-6-21 18:04
看看怎么回事

---

作者: tbmbx2017    时间: 2016-9-11 04:20
厉害，相当可以的了

---

作者: taofan    时间: 2016-9-13 19:59
入会费入会费

---

作者: whh12345678    时间: 2017-6-10 16:26
厉害

---

作者: apoul    时间: 2017-12-25 07:47
谢谢分享

---

欢迎光临 TC官方合作论坛 (http://bbs.52tc.co/)

Powered by Discuz! X3.1