2001 USACO 绿组 奶牛表达式 (要求用PASCAL语言编写)在数学中同一个表达式常有几种写法,其中中缀表式是最常见的,如1+2和7*（5-3）.而在前缀表达式中,运算符式写操作数之前的,如上述的表达式的
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/08 00:43:11
2001 USACO 绿组 奶牛表达式 (要求用PASCAL语言编写)在数学中同一个表达式常有几种写法,其中中缀表式是最常见的,如1+2和7*（5-3）.而在前缀表达式中,运算符式写操作数之前的,如上述的表达式的
2001 USACO 绿组 奶牛表达式 (要求用PASCAL语言编写)
在数学中同一个表达式常有几种写法,其中中缀表式是最常见的,如1+2和7*（5-3）.而在前缀表达式中,运算符式写操作数之前的,如上述的表达式的前缀写法是+12和*7-53.同样地,在后缀表达式不需要也不承认括号.
前缀和后缀表达式也不予要承认括号.
而奶牛表达式是一种前缀,中缀和后缀的混合书写表达式,使用单个数字和二元运算符+,-.一个奶牛表达式可以用任何中缀,前缀和后缀的混合规则加以解释.
例如表达 +54+-82至少能按两种不同的方式求值
+54+-82=9+-82=9+6=15
+54+-82=+9-82=+12=3
表达式9-4+3在奶牛表达式中结果既可以是2,也可以是8
现在各你一个奶牛表达式,要求算出它可能的不同结果的数目.给出的表达式一定是合法的.
输入说明
一个不超过80个字符的文本字符串,代表一个合法的奶牛表达式,该字串符不包括空格
输出说明
可能的结果数目
输入样例
+54-82
输出样例
2
2001 USACO 绿组 奶牛表达式 (要求用PASCAL语言编写)在数学中同一个表达式常有几种写法,其中中缀表式是最常见的,如1+2和7*（5-3）.而在前缀表达式中,运算符式写操作数之前的,如上述的表达式的
没时间去写了.
我的感觉是记搜,
定义f(a,b)为第a位到第b位之间这一段算式的可能数.
如果b-a>1且[a,b]段没有运算符,f(a,b)返回0即没有可能.
如果b-a=1且[a,b]为数字.返回1.
否则前头有运算符的,划分为前缀,后头有运算符的划分为后缀,其余中间的运算符划分为中缀,
以这三种方式划分,然后穷举每一种可能下,两个运算目的划分点,进行递归处理,把返回的f值相加即可.需要注意的是运算顺序,如果能用前缀,就不需要划分同样运算目的中缀,因为加减之间没有优先级,所以前中后缀只要运算目一样,结果都一样,就不需要重复算了.