【有源码】栈的典型应用-带你探秘tc表达式括号匹配

rainshine

午后的阳光真暖和那，大家有木有在睡午觉呢。~~~
哇哈哈好自豪好几篇都是我文章呢。啦啦。谢谢看官们的支持。rainshine会继续努力，写更多的实用函数，公开更多好的源码！！
今天带来的公开例程：


引言：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！


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


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

游客，如果您要查看本帖隐藏内容请回复

zxw445

- -，好厉害的大神，佩服佩服。。。。。求大神教我。。。。

美珍子

你整天泡在这里。你想当官了。

rainshine

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

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

rainshine

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

。。。。

qisi2012

顶上。。感谢分享

as128214121

好，{:soso_e113:}

美珍子

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

rainshine

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

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