设计内容:
设计一个程序,把中缀表达式转换成一棵二叉树,然后通过后序(根)遍历计算表达式的值。
设计要求:
对于输入的一个中缀表达式,判断表达式是否合法。(表达式的输入符合四则运算的显示规范)
如果合法,把中缀表达式转换成一棵二叉树。(创建二叉链表,数据结构为二叉链表)
通过后序(根)遍历计算表达式的值,输出运算结果。(表达式求值)
需要注意的是,合法表达式不能为空,可以出现在表达式中的字符有:
运算符“+”、“-”、“*”、“/”;
左右括号“(”、“)”;
整数(可以是多位的);(难点:如何识别?)
空格符和制表符。
测试用例:20 + ( 3 * ( 4 + 46 ) – 6 )/2 - 134
预期测试结果:-42
运行截图: