【程序填空】表达式计算(栈应用)C++
温馨提示:本题为深大OJ原题,深大的同学请勿直接抄袭,以免出现多个代码相同以致评0分的情况,代码和思路仅供参考,希望大家能逐步成长。
目录
题目描述
思路分析
AC代码
题目描述
使用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
int j = 0;
while (c != '#' || OPTR.top() != '#') {
if (In(c, OPSET)) {
if (x) {
TempData[j] = '\0';
sscanf(TempData, "%lf", &Data);
OPND.push(Data);
strcpy(TempData, "\0");
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
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];
}