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

wangqi0021

)))

mik

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

这样做的目的是?

是要算出结果?  还是要输出 " a+b+c" 这个字符串?

要输出这条字符串,肯定要先找出每一个 '(' 和 ')'  得出最内层的括号, 判断括号两边的运算符

Wind-Son

语法分析范畴
可借助yacc和Bsion一类的语法工具

emuer

我说一个比较苯的方法，从左到右分析输入的公式，当遇到一对匹配的括号时，对比去括号版本和带括号版本的计算结果，如果相同，就把该对括号去掉，不相同就保留并标记该对括号不可去除。

例如 (a+(b+c)*d.......对比a+b+c*d的结果。这只是个很初步的想法，还是有很多要work on的地方，但也许有用吧

emuer

原帖由 converse 于 2008-1-17 14:01 发表
比较括号左边和右边的第一个运算符是不是同一个优先级的就是了.

这样会认为 a+(b+c)*d 的括号认为是可以去除的。

cheng_lai_shun

恩，栈应该可以

redspider

原帖由 flw 于 2008-1-17 14:05 发表
我觉得应该先把多余的叹号去掉。

  我也这么认为

1. s/!\+/!/

复制代码

yovn

现转成后缀表达式，然后就是一个后序转中序表达式的问题。

cjaizss

建立每对括号内的符号标准（姑且先叫这个名字吧）
比方
(a+b)为+
(a*b)为*
(a-b+c)为-
(a/b)为/
(a*（b+C）)为*
((....))为()
然后再去找前后紧接着的符号
按照这个思路再走，我想出来了，但希望LZ继续想

zszyj

原帖由 Wind-Son 于 2008-1-19 01:03 发表
语法分析范畴
可借助yacc和Bsion一类的语法工具

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

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

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 于 2008-2-14 23:44 编辑 ]