带有括号的表达式计算

带括号的表达式求值(nyoj35)

描述

ACM队的mdd想做一个计算器，但是，他要做的不仅仅是一计算一个A+B的计算器，他想实现随便输入一个表达式都能求出它的值的计算器，现在请你帮助他来实现这个计算器吧。比如输入：“1+2/4=”，程序就输出1.50（结果保留两位小数）

输入

第一行输入一个整数n，共有n组测试数据（n数据保证输入的操作数中不会出现负数。数据保证除数不会为0

输出

每组都输出该组运算式的运算结果，输出结果保留两位小数。

样例输入

21.000+2/4=((1+2)*5+1)/4=

样例输出

1.504.00

题目网址：http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=35

题目分析：

首先，我们要留意这题是有括号的，以前做过没有括号的表达式求值，直接用递推或者递归就能求解（提交在12服务器，找不到源代码了），但是这题用递归或者递推却很难求解。于是，我还是百度了一下大牛们的做法，他们的方法如下：

将中缀表达式转化成后缀表达式（即逆波兰表达式）

对后缀表达式进行计算 看到这里，你可能会懵逼了，什么是中缀表达式？什么是后缀表达式？为什么要转化成后缀表达式？别急，下面我会一一解释。

中缀表达式（中缀记法）中缀表达式是一种通用的算术或逻辑公式表示方法，操作符以中缀形式处于操作数的中间。中缀表达式是人们常用的算术表示方法。‘后缀表达式：指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则）。虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式却是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。对计算机来说，计算前缀或后缀表达式的值非常简单。

ok，下面我再介绍怎么把中缀表达式转化成后缀表达式：

转换过程需要用到栈，具体过程如下：1）如果遇到操作数，我们就直接将其输出。2）如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。3）如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出。4）如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到" ) "的情况下我们才弹出" ( "，其他情况我们都不会弹出" ( "。5）如果我们读到了输入的末尾，则将栈中所有元素依次弹出。

(是不是看完一脸懵逼？？？没事，下面我来解释一下：比如我现在的中缀表达式为：2*(2+3)，则设用hou来表示后缀表达式，s表示储存符号的栈结构。下面开始分析：1.读到2，是数字，直接放入hou，此时hou和s的情况是:h: 2s: (表示空）2.读到 * ，因为一开始s没有符号，所以把 * 放入s，此时hou和s的情况是:hou: 2s: *3.读到括号，所以直接放入s，此时hou和s的情况是:hou：2s： * (4.读到2，是数字，直接放入hou，此时hou和s的情况是:hou: 2 2s: * (5.读到+,因为前一个是(，所以就直接放入s，此时hou和s的情况是:hou: 2 2s: * ( +6.读到3，是数字，直接放入hou，此时hou和s的情况是:hou: 2 2 3s: * ( +7.读到)，此时对s进行pop,知道遇见(，pop出的元素放在hou，此时hou和s的情况是:hou：2 2 3 +s: *8.把剩下的符号放在hou,此时hou和s的情况是:hou: 2 2 3 + *s:所以此时就结束了，后缀表达式为2 2 3 + *

那么如何计算后缀表达式呢？

规则如下：(1)如果是操作数，则放入栈中；(2)如果是操作符，则取出栈中两个操作数，进行运算后，将结果放入栈中；(3)直到最后栈中只有一个元素，此元素就是计算结果；下面对上述后缀表达式进行计算:1.从左向右扫描，首先扫描到+，所以把前两个数pop出来，并假设为x=3,y=2则y+=x，此时y=5，再把 y push回去，此时后缀表达式变成2 5 *2.从左向右扫描，首先扫描到，所以把前两个数pop出来，并假设为x=5,y=2则y=x，此时y=10，再把 y push回去，此时后缀表达式变成10此时已经计算结束，所求结果为10，即2*(2+3)=10

代码（也就180行左右）

源代码：https://paste.ubuntu.com/p/SzXYWd8t7P/

参考文献：1.百度百科2.https://blog.csdn.net/sgbfblog/article/details/80016513.https://blog.csdn.net/xiazdong/article/details/72726934.https://www.cnblogs.com/dolphin0520/p/3708602.html