Pro.ID1326 Title利用二叉树对表达式求值 Title链接http://10.20.2.8/oj/exercise/problem?problem_id=1326 AC8 Submit164 Ratio4.88% 时间&空间限制描述把一条正常表示的算术表达式(即中缀表达式),存储为一棵二叉树,然后对这棵二叉树进行后序遍历,即可得到该表达式的后缀表达式形式。然后就可利用前面所学知识对该表达式求值。 如有中缀表达式:(a+b)*c-d/e ,转为后缀表达式后:ab+c*de/- 。 在把中缀表达式存储为二叉树的过程中,考虑到有括号的存在、以及运算符的优先级别,需要用到函数precede(),因此提供该函数所用到的"算符优先关系表"如下: 上表包含了幂运算"^",其中的除法"/"是整数除法,即结果不含小数点。其中的i即表示运算数。 请对所给出的表达式进行求值。 输入有多个测试用例:每个表达式占一行。表达式中的运算数均为一位的正整数。表达式中不含空格,表达式最后以'#'表示结束。 不保证所有表达式都合法。表达式长度不超过1000个字符。 输出Description 把一条正常表示的算术表达式(即中缀表达式),存储为一棵二叉树,然后对这棵二叉树进行后序遍历,即可得到该表达式的后缀表达式形式。然后就可利用前面所学知识对该表达式求值。 如有中缀表达式:(a+b)*c-d/e ,转为后缀表达式后:ab+c*de/- 。 在把中缀表达式存储为二叉树的过程中,考虑到有括号的存在、以及运算符的优先级别,需要用到函数precede(),因此提供该函数所用到的"算符优先关系表"如下: 上表包含了幂运算"^",其中的除法"/"是整数除法,即结果不含小数点。其中的i即表示运算数。 请对所给出的表达式进行求值。 Input 有多个测试用例:每个表达式占一行。表达式中的运算数均为一位的正整数。表达式中不含空格,表达式最后以'#'表示结束。 不保证所有表达式都合法。表达式长度不超过1000个字符。 Output 对每个表达式输出一行结果:该表达式的运算结果。如该表达式合法,则保证运算结果在32-bit整数范围之内。 如该表达式不合法,请输出一行 "ERROR" 。 Sample Input (3+2)*8-9/4# Sample Output 38 Hint (4-2)/(1-7/7)# 这个表达式导致"除0" Author 样例输入(3+2)*8-9/4# 样例输出38 提示(4-2)/(1-7/7)# 这个表达式导致"除0" 作者 |