今天在网上看到了一个求助贴关于这类问题,以前曾经做过,就抛出一个方案出来。

  什么是算式符号匹配:

[((a+b)+(a+c))+a]*(a+b)

如上所示的一个算式,你需要首先确保这个算式符号是匹配的,而这个匹配又如何实现?也就是说,你有”(“,我后面一定要有一个”)”相匹配,而且又一定要 是成对关系存在。那么这个问题直接衍生出来的就是许多智能IDE,如eclipse是如何解析你的符号正确问题

 

如  public void method(String s)

{

……

现在这个方法是少了一个“}”,那么IDE就会出现错误提示,而这种和上面所说的算式解析是一个原理,其实也很简单,那么我的解决思路,就是用最典型的栈数据结构

关于栈

众所周知,栈是后进先出,也就是你永远只能取出最后一个进入栈中的数据,栈的应用范围也相当广,比如说我们很熟悉的 计算器,计算器是从最低位开始计算的,而我们的输入方式却是从最高位开始输入,比如100,我们首先输入的是1,而不是最后一位0,那么栈在这种情况下将 会带来极大的便利性。那么栈又是如何处理此类符号匹配问题呢?

思路:

其实只要想到了栈,后面都相当简单,这个基本上没有什么复杂度。首先进行依次对此数据的遍历,在此以”(a+b)” 为例,当遇到了需要判断的符号(此处为'(‘),则将此字符压入栈中,当遇到了与其成对的符号”)”,则抛出栈顶元素,并将栈顶元素与当前游标所指的字符 比较,若是成功则匹配,不成功,则需要在此处进行提示错误。

那么,(((a+b)]),此表达式的判断行为如下:

1.(,压入栈中,

2.(,压入栈中,

3.(,压入栈中,

4.a,跳过

………

7,),与栈顶元素“(”相匹配,跳过,移出当前栈顶

8,],与栈顶元素不匹配,抛出错误……..

以上就是算法行为过程,其实思路很简单,当然,我不知道对于此类问题有什么更好的解决方案,若有,欢迎指正。呵呵~

CODE:

不想写了,过几天更新这个CODE吧,代码不在本机上,难的写。我有点懒,你懂的。其实关键在于栈的构造,主要是两个方法,一个push,将元素压入栈中,并置顶,一个POP,将栈顶移出。

Leave a Reply

Your email address will not be published. Required fields are marked *

%d bloggers like this: