去括号！！！！！！！！！！！！！

zszyj

原帖由 hopeclassshych 于 2008-1-17 13:23 发表
一个数学表达式，其中只含有＋－＊／还有（）五种运算符注意括号嵌套例
(a+(c+d))+e
求一个算法去掉多余的括号！！！！！！！！！！

看看这个http://bbs.chinaunix.net/thread-1043833-1-1.html

dxcnjupt

回楼上
指定的主题不存在或已被删除或正在被审核，请返回

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
支持前面对比运算符优先级的算法。

1提取括号内优先级最小的运算符k（要考虑多重括号的问题）
2对比k和括号左右两边的运算符p1、p2
3若k优先级大于等于p1和p2则括号可去掉。－－大于表示不会影响运算顺序，等于虽然会影响运算顺序，但是同优先级算术运算都满足结合率。
－－－－－－－－－－－－－
说错了....../ 和 *不满足结合率

[ 本帖最后由 dxcnjupt 于 2008-2-16 11:52 编辑 ]

Edengundam

原帖由 yovn 于 2008-2-13 11:07 发表
现转成后缀表达式，然后就是一个后序转中序表达式的问题。

一语中的啊.

zszyj

原帖由 dxcnjupt 于 2008-2-15 16:31 发表
回楼上
指定的主题不存在或已被删除或正在被审核，请返回

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
支持前面对比运算符优先级的算法。

1提取括号内优先级最小的运算符k（要考虑多重括号的问题）
2对比k和括号 ...

很奇怪, 昨晚还能回该贴,今天就不见了.
因为有人提出可以通过使用YACC和LEX在进行语法分析过程中去掉不必要的括号, 但我认为因为语法树的建立过程是编程人员无法干预的,因为比较困难. 但有一个比较笨的方法, 就是通过穷举各种存在多余括号的语法模式, 使用yacc和LEX来实现该方法, 例子如下:

statement:
  
    expr '+'  '(' expr '+' expr ')' { output expr '+' expr '+' expr; }  // output 为伪代码,实际实现时可以需要改写为C代码;
|  expr '+'  '(' expr '*' expr ')' { output expr '*' expr '*' expr; }
|  expr '+'  '(' expr '-' expr ')' { output expr '+' expr '*' expr; }
|  expr '+'  '(' expr '/' expr ')' { output expr '+' expr '*' expr; }
|  expr '*'  '(' expr '*' expr ')' { output expr '+' expr '*' expr; }
|  expr '*'  '(' expr '/' expr ')' { output expr '+' expr '*' expr; }
...

后面的省略号是指LZ可以继续列举其它以'-'和'/'为第一操作符的语法模式, 只要列举全了,就能实现LZ的要求了.

[ 本帖最后由 zszyj 于 2008-2-15 22:46 编辑 ]

Wind-Son

原帖由 zszyj 于 2008-2-14 23:36 发表

我个人感觉, 这个问题有一定难度, 用语法分析可以定义操作符的优先级, 但似乎做不到将多余括号去掉.

不过, 当然, 我们也可以用一种笨方法, 就是将所有存在多余括号的模式都列出来,然后将其去掉, 例如以下模式:

expr  '+'   '('  expr  ')':  output( expr '+' expr );
|  expr  '-'   '('  expr  ')':  output( expr '-' expr );
| expr  '*'   '('   expr  '*'  expr  ')':  output( expr '*' expr  '*' expr);
| expr  '*'   '('   expr  '/'  expr  ')':  output( expr '*' expr  '/' expr);
....

这是一种人手提前将各种可能出现的多余括号模式穷举了的笨方法, 而不是在建立语法事的过程中,模拟语法分析的比较来去掉括号的方法, 可用,但不智能.
..

穷举当然不是办法.
楼主只是要求表达式等价.那么可以先生成表达式的语法树,所有的括号全部去调,然后重新自顶向下展开,在展开过程中,如果某个节点的子树的树根对应的算符优先级比该节点低,则添置括号

zszyj

原帖由 Wind-Son 于 2008-2-15 23:36 发表


穷举当然不是办法.
楼主只是要求表达式等价.那么可以先生成表达式的语法树,所有的括号全部去调,然后重新自顶向下展开,在展开过程中,如果某个节点的子树的树根对应的算符优先级比该节点低,则添置括号

呵呵, 自已编码分析表达式并构建语法树并完成测试,即使精通编译原理的高手恐怕也得一周时间吧,更别说LZ是否有能力完成这个任务了.

而四则运算的等价语法模式也不过10来种,只需要几分钟时间, 有现成的语法分析辅助工具而不用? 呵呵,LZ自已看着办就是了.

另外, 补充更正一点, 我列出的语法模式, 考虑到expr是递归语法定义, 因此应该把第一行的statememt改为expr, 即表达式之间的四则运算也是表达式,同样存在需要去掉括号的操作.

zszyj

原帖由 Wind-Son 于 2008-2-15 23:36 发表


穷举当然不是办法.
楼主只是要求表达式等价.那么可以先生成表达式的语法树,所有的括号全部去调,然后重新自顶向下展开,在展开过程中,如果某个节点的子树的树根对应的算符优先级比该节点低,则添置括号

再细想一下, Wind-Son所说的先去括号,然后根据父子结点之间的算符优先级的方法是欠考虑的,只通过父结点优先级高于子结点则加括号是不完整的,同样存在我前面据说的穷举所有加括号的语法模式问题. 例如以下几个模式父子结点优先级相同,但却要加括号:
父结点是'/'而子结点是"*", 则要加括号, 证明: a/(b*c) != a/b*c;
父结点是'-'而子结点是'+', 也要加括号,证明:a-(b+c) != a-b+c;
....
这样, 与我用语法模式表达的穷举有什么两样? 不过是用大量的if判断代替了语法模式来穷举而已．

Wind-Son

原帖由 zszyj 于 2008-2-16 11:04 发表

呵呵, 自已编码分析表达式并构建语法树并完成测试,即使精通编译原理的高手恐怕也得一周时间吧,更别说LZ是否有能力完成这个任务了.

而四则运算的等价语法模式也不过10来种,只需要几分钟时间, 有现成的语法分析辅助工具而不用? 呵呵,LZ自已看着办就是了.

另外, 补充更正一点, 我列出的语法模式, 考虑到expr是递归语法定义, 因此应该把第一行的statememt改为expr, 即表达式之间的四则运算也是表达式,同样存在需要去掉括号的操作.

原帖由 zszyj 于 2008-2-16 11:24 发表

再细想一下, 如果某个节点的子树的树根对应的算符优先级比该节点低,则添置括号,只通过父结点优先级高于子结点则加括号是不完整的,同样存在我前面据说的穷举所有加括号的语法模式问题. 例如以下几个模式父子结点优先级相同,但却要加括号:
父结点是'/'而子结点是"*", 则要加括号, 证明: a/(b*c) != a/b*c;
父结点是'-'而子结点是'+', 也要加括号,证明:a-(b+c) != a-b+c;
....
这样, 与我用语法模式表达的穷举有什么两样? 不过是用大量的if判断代替了语法模式来穷举而已．

我什么时候说要手动分析了，设计好文法，用yacc不就行了？
还有，你说的“Wind-Son所说的先去括号,然后根据父子结点之间的算符优先级的方法是欠考虑的”，我原话更正一下：
“如果某个节点的子树的树根对应的算符优先级比该节点低或相等,则添置括号”
形式化的递归文法一般都是可以避免穷举的

zszyj

原帖由 Wind-Son 于 2008-2-16 11:42 发表




我什么时候说要手动分析了，设计好文法，用yacc不就行了？
还有，你说的“Wind-Son所说的先去括号,然后根据父子结点之间的算符优先级的方法是欠考虑的”，我原话更正一下：
“如果某个节点的子树的树 ...

设计好文法? 我的理解就是定义好词法和语法了, 那么等于就是我的方法, 而根本不是在语法树中删除括号结点, 因为YACC生成的语法树,你是无法操作的.

至于你说的,优先符相等也要加括号, 那就不是解决LZ的问题,而是给LZ创造麻烦了. 因为楼主本来就是希望不必要的括号去掉,而你的方案是增加括号了,举例来说:
父子节点都是'+', 本来是a+b+c,最后就变成了a+(b+c).

呵呵,说话不要太冲动, 思考成熟了再发言不迟

Wind-Son

原帖由 zszyj 于 2008-2-16 20:33 发表

设计好文法? 我的理解就是定义好词法和语法了, 那么等于就是我的方法, 而根本不是在语法树中删除括号结点, 因为YACC生成的语法树,你是无法操作的.

至于你说的,优先符相等也要加括号, 那就不是解决LZ的问题,而是给LZ创造麻烦了. 因为楼主本来就是希望不必要的括号去掉,而你的方案是增加括号了,举例来说:
父子节点都是'+', 本来是a+b+c,最后就变成了a+(b+c).

呵呵,说话不要太冲动, 思考成熟了再发言不迟

好歹也要知道我在说什么吧, 我只不过是建议楼主使用现成的工具而已. 你举的例子不管用哪种方法都是要处理的.
正题:
第一 你好像不太了解分析树和语法树的区别,编译器一般会生成比分析树更紧凑的语法树, 像括号这样的东西早已隐含在语法树中, 根本不必显式地生成你所谓的"括号节点".  如a-(b-c)直接生成
              -
           /     \
          a      -
                /   \
               b    c
第二 你好像也没有真正用过YACC, YACC生成的语法树, 你是可以操作的. 何处真正生成语法节点执行相应动作完全是可控的.
第三 你举的例子没有问题, 写个伪代码吧,请不要纠缠细节, 程序调试那是楼主的任务. 你只需要说明这种方法是否可行
for (自顶向下遍历语法树) {
     if  (子节点比父节点优先级高)
          PASS
     else if  (子节点比父节点优先级低)
         对子节点加括号
   else if (父节点为-或/)
         对右子节点加括号
}

[ 本帖最后由 Wind-Son 于 2008-2-16 23:30 编辑 ]