温馨提示：本题为深大OJ原题，深大的同学请勿直接抄袭，以免出现多个代码相同以致评0分的情况，代码和思路仅供参考，希望大家能逐步成长。
题目描述
使用C 自带的stack栈模板来实现四则运算表达式求值
算法描述参考第3.2.5节
算法伪代码参考P53-54的算法3.4
例如
1. Push (OPTR, '#');表示把字符#压入堆栈OPTR中，转换成c 代码就是OPTR.push('#');
2. Pop(OPND, a); 表示弹出栈OPND的栈顶元素，并把栈顶元素放入变量a中。因此改成c 代码是两个操作：a = OPND.top(); OPND.pop();
3. a = GetTop(OPND)表示获取栈OPND的栈顶元素，转成c 代码就是： a = OPND.top();
大家主要是改造表达式求值函数EvaluateExpression的代码
输入
第一个输入t，表示有t个实例
第二行起，每行输入一个表达式，每个表达式末尾带#表示结束
输入t行
输出
每行输出一个表达式的计算结果，计算结果用浮点数（含2位小数）的格式表示
参考代码如下：
#include <iostream> #include<iomanip> using namespace std; int main() { double temp = 12.345678 cout<<fixed<<setprecision(2)<<temp<<endl; }
输出结果为12.35
输入样例1
2 1 2*3-4/5# (66 (((11 22)*2-33)/3 6)*2)-45.6789#
输出样例1
6.20 54.32
提示
本题需要把一个字符串转成浮点数，例如字符串"1.234"转成浮点数1.234
因为C 11开始取消atof函数，所以C 要用sscanf函数来实现该转换，参考代码如下
#include <iostream> #include <cstdio> using namespace std; int main() { char TempData[]="1.23456"; double dd; sscanf(TempData, "%lf", &dd); cout<<dd<<endl; return 0; }
思路分析
思想及其巧妙，一个栈存操作数，一个栈存运算符，主要的思路就是，把优先级低的运算符和其对应的操作数压入栈，先算优先级高的操作数。
具体来说是这样的一种操作：
遍历算式，如果是数，压入操作数栈，如果是运算符，先判断这个运算符和运算符栈栈顶的运算符的优先级，如果新来的优先级更高（像 * 和 / ），直接压入栈，如果新来的更低（ 和 - ），那么需要开始计算这个运算符前面的数值，即两次弹出操作数栈栈顶元素用来计算，计算的运算符是当前运算符栈顶元素。
主要流程是这样，然后需要注意的是，这个算式是一个字符串，操作数也是一个字符串，这里就需要我们将字符串变成实数，比较巧妙的是，操作符前面一定是操作数，所以遇到操作符即遇到了操作数的结尾。
更巧妙的是这个运算符优先级的二维数组，居然可以这样比较优先级@_@。
AC代码
代码块1
代码语言：javascript复制 int j = 0;
while (c != '#' || OPTR.top() != '#') {
if (In(c, OPSET)) {
if (x) {
TempData[j] = ' ';
sscanf(TempData, "%lf", &Data);
OPND.push(Data);
strcpy(TempData, " ");
j = 0;
}
switch (precede(OPTR.top(), c)) {
case '<':
OPTR.push(c);
c = MyExp[ i];
break;
case '=':
OPTR.pop();
c = MyExp[ i];
break;
case '>':
a = OPND.top();
OPND.pop();
b = OPND.top();
OPND.pop();
OPND.push(Operate(b, OPTR.top(), a ));
OPTR.pop();
x = 0;
break;
}
} else {
TempData[j ] = c;
c = MyExp[ i];
x = 1;
}
}
return OPND.top();代码块2
代码语言：javascript复制double Operate(double a, unsigned char theta, double b) { //计算类似a b的表达式结果
if (theta == ' ')return a b;
if (theta == '-')return a - b;
if (theta == '*')return a * b;
return a / b;
}
bool In(char Test, char* TestOp) { //判断字符Test是否是运算符，是则返回true
if (Test == ' ' || Test == '-' || Test == '*' || Test == '/' || Test == '(' || Test == ')' || Test == '#')return true;
return false;
}
char precede(char Aop, char Bop) { //返回两个运算符优先级的比较结果
int i, j;
switch (Aop) {
case' ':
i = 0;
break;
case'-':
i = 1;
break;
case'*':
i = 2;
break;
case'/':
i = 3;
break;
case'(':
i = 4;
break;
case')':
i = 5;
break;
case'#':
i = 6;
break;
}
switch (Bop) {
case' ':
j = 0;
break;
case'-':
j = 1;
break;
case'*':
j = 2;
break;
case'/':
j = 3;
break;
case'(':
j = 4;
break;
case')':
j = 5;
break;
case'#':
j = 6;
break;
}
return Prior[i][j];
}
