第1关:基于栈的中缀算术表达式求值
任务描述
本关任务:输入一个中缀算术表达式,求解表达式的值。运算符包括+、-、*、/、(、)、=,参加运算的数为double类型且为正数。(要求:直接针对中缀算术表达式进行计算,不能转换为后缀或前缀表达式再进行计算,只考虑二元运算即可。)
编程要求
输入
多组数据,每组数据一行,对应一个算术表达式,每个表达式均以“=”结尾。当表达式只有一个“=”时,输入结束。参加运算的数为double类型。
输出
对于每组数据输出一行,为表达式的运算结果。输出保留两位小数。
测试说明
平台会对你编写的代码进行测试:
测试输入:
2+2=
20*(4.5-3)==
预期输出:
4.00
30.00
#include <iostream>
#include<iomanip>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
using namespace std;
typedef struct
{//运算符栈
char *base;
char *top;
int stacksize;
}SqStack1;
Status InitStack1(SqStack1 &S)
{//运算符栈初始化
S.base = new char[MAXSIZE];
if (!S.base)
return OVERFLOW;//分配失败
S.top = S.base;
S.stacksize = MAXSIZE;
return OK;
}
Status Push1(SqStack1 &S, char e)
{//运算符栈入栈
if (S.top - S.base >= S.stacksize)
return ERROR; // 栈溢出
*S.top = e;
S.top++;
return OK;
}
Status Pop1(SqStack1 &S)
{//运算符栈出栈
if (S.top == S.base)
return ERROR;//栈已空
S.top--;
return OK;
}
char GetTop1(SqStack1 S)
{//运算符栈取栈顶元素
if (S.top == S.base)
return ERROR;//栈已空
return *(S.top-1);
}
typedef struct
{//操作数栈
double *base;
double *top;
int stacksize;
}SqStack2;
Status InitStack2(SqStack2& S)
{//操作数栈初始化
S.base = new double[MAXSIZE];
if (!S.base)
return ERROR;
S.top = S.base;
S.stacksize = MAXSIZE;
return OK;
}
Status Push2(SqStack2& S, double e)
{//操作数栈入栈
if (S.top - S.base >= S.stacksize)
return OVERFLOW;
*S.top++ = e;
return OK;
}
Status Pop2(SqStack2& S)
{//操作数栈出栈
if (S.top == S.base)
return ERROR;//栈已空
S.top--;
return OK;
}
double GetTop2(SqStack2 S)
{//操作数栈取栈顶元素
if (S.top == S.base)
return ERROR;//栈已空
return *(S.top - 1);
}
double Calculate(double a, char op, double b)
{//计算表达式“a op b”的值
switch (op)
{
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
default:
return 0;
}
}
char Precede(char a, char b)
{//比较运算符a和b的优先级
char precede[7][7] = {
//+ - * / ( ) =
{'>','>','<','<','<','>','>'},// +
{'>','>','<','<','<','>','>'},// -
{'>','>','>','>','<','>','>'},// *
{'>','>','>','>','<','>','>'},// /
{'<','<','<','<','<','=','X'},// (
{'>','>','>','>','X','>','>'},// )
{'<','<','<','<','<','X','='} // =
};
int i=0;
int j=0;
switch (a)
{
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 (b)
{
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 precede[i][j];
}
double EvaluateExpression(SqStack1 OPTR,SqStack2 OPND,char s[])
{//算术表达式求值的算符优先算法
//设OPTR和OPND分别为运算符栈和操作数栈
//表达式求值算法调用Precede函数和Calculate函数
char* ch = s;
double a, b;
char tempop;
while (*ch!='='||GetTop1(OPTR) != '=')
{
if ((*ch >= '0' && *ch <= '9')||*ch=='.') {//处理数字
double num;
double bignum=0;
double smallnum = 0;
// 读取多位数字及小数
//小数点之前的部分
while (*ch >= '0' && *ch <= '9') {
bignum = bignum * 10 + (*ch - '0');
ch++;// 读取下一个字符
}
//小数点之后的部分
if (*ch == '.') {
ch++;
while (*ch >= '0' && *ch <= '9') {
smallnum += (*ch - '0')*0.1;
ch++;// 读取下一个字符
}
}
num = bignum + smallnum;
Push2(OPND, num);
}
else//处理运算符
{
switch (Precede( GetTop1(OPTR), *ch))
{
case '<':
Push1(OPTR, *ch);
ch++;
break;
case '>':
tempop = GetTop1(OPTR);
Pop1(OPTR);
b = GetTop2(OPND);
Pop2(OPND);
a = GetTop2(OPND);
Pop2(OPND);
Push2(OPND, Calculate(a,tempop,b));
break;
case '=':
Pop1(OPTR);
ch++;
break;
}
}
}
return GetTop2(OPND);
}
int main()
{//设OPTR和OPND分别为运算符栈和操作数栈
SqStack1 OPTR;
InitStack1(OPTR); //初始化OPND栈
SqStack2 OPND;
InitStack2(OPND); //初始化OPTR栈
Push1(OPTR,'='); //提前在OPTR栈中放入'=',便于以后比较符号优先级
char s[100];
while(cin>>s)
{//循环读入多组数据
if(s[0]=='=')
break; //当表达式只有一个“=”时,输入结束
//输出中缀算术表达式的值
cout<<fixed<<setprecision(2)<<EvaluateExpression(OPTR,OPND,s)<<endl;
}
return 0;
}
算法步骤:
设定两栈 :OPND—–操作数或运算结果 OPTR——运算符
① 初始化OPTR栈和OPND栈,将表达式起始符“#”压入OPTR栈。
② 扫描表达式,读入第一个字符ch,如果表达式没有扫描完毕至“#”或OPTR的栈顶元素不为“#”时,则循环执行以下操作:
- 若ch不是运算符,则压入OPND栈,读入下一字符ch;
- 若ch是运算符,则根据OPTR的栈顶元素和ch的优先级比较结果,做不同的处理:
- 若是小于,则ch压入OPTR栈,读入下一字符ch;
- 若是大于,则弹出OPTR栈顶的运算符,从OPND栈弹出两个数,进行相应运算,结果压入OPND栈;
- 若是等于,则OPTR的栈顶元素是“(”且ch是“)”,这时弹出OPTR栈顶的“(”,相当于括号匹配成功,然后读入下一字符ch。
③ OPND栈顶元素即为表达式求值结果,返回此元素。
第2关:中缀表达式转化为后缀表达式
任务描述
本关任务:输入一个中缀算术表达式,将其转换为后缀表达式。运算符包括+、-、*、/、(、)、=,参加运算的为小于10的自然数。(只考虑二元运算即可)
编程要求
输入
多组数据,每组数据一行,对应一个算术表达式,每个表达式均以“=”结尾。当表达式只有一个“=”时,输入结束。
输出
对于每组数据输出一行,为表达式的后缀式。
测试说明
平台会对你编写的代码进行测试:
测试输入:
9+(3-1)*3+1/2=
1+2=
=
预期输出:
931-3*+12/+
12+
源码:
#include<iostream>
using namespace std;
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef struct
{
char* base;
char* top;
int stacksize;
}SqStack;
Status InitStack(SqStack& S)
{//初始化栈
S.base = new char[MAXSIZE];
if (!S.base)
return ERROR;
S.top = S.base;
S.stacksize = MAXSIZE;
return OK;
}
Status Push(SqStack& S, char e)
{//入栈
if (S.top - S.base >= MAXSIZE)
return OVERFLOW;
*S.top = e;
S.top++;
return OK;
}
Status Pop(SqStack& S)
{//出栈
if (S.top == S.base)
return ERROR;
S.top--;
return OK;
}
char GetTop(SqStack S)
{//取栈顶元素
if (S.top == S.base)
return 'E';
return *(S.top - 1);
}
char Precede(char a, char b)
{//比较运算符a和b的优先级
char precede[7][7] = {
//+ - * / ( ) =
{'>','>','<','<','<','>','>'},// +
{'>','>','<','<','<','>','>'},// -
{'>','>','>','>','<','>','>'},// *
{'>','>','>','>','<','>','>'},// /
{'<','<','<','<','<','=','X'},// (
{'>','>','>','>','X','>','>'},// )
{'<','<','<','<','<','X','='} // =
};
int i = 0;
int j = 0;
switch (a)
{
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 (b)
{
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 precede[i][j];
}
void InfixToSuffix(SqStack OPTR, char s[])
{//将中缀表达式转化为后缀表达式并输出
int num;
char* ch = s;
char tempop;
while (*ch != '=') {
if (*ch >= '0' && *ch <= '9') {//是数字直接输出
cout << *ch;
ch++;
}
else {//运算符处理
if (*ch == '(') {//左括号直接入栈
Push(OPTR, *ch);
ch++;
}
else if (*ch == ')') {//右括号则出栈至上一个左括号
while (GetTop(OPTR) != '(') {
cout << GetTop(OPTR);
Pop(OPTR);
}
Pop(OPTR);//所匹配的左括号出栈
ch++;
}
else {//其他运算符则循环判断优先级,栈顶符号大于等于当前符号,则输出栈顶,当前符号入栈
while (Precede(GetTop(OPTR), *ch) == '>' || Precede(GetTop(OPTR), *ch) == '=') {
cout << GetTop(OPTR);
Pop(OPTR);
}
Push(OPTR, *ch);
ch++;
}
}
}
// 将栈中剩余的操作符弹出
while (OPTR.top != OPTR.base) {
if (GetTop(OPTR) != '=') { // 避免输出栈底的 '='
cout << GetTop(OPTR);
}
Pop(OPTR);
}
cout << endl;
}
int main()
{
SqStack OPTR;
InitStack(OPTR); //初始化操作符栈OPTR
Push(OPTR, '='); //先在栈底放入'='便于以后比较符号优先级
char s[100];
while (cin >> s)
{
if (s[0] == '=')
break; //当表达式只有一个“=”时,输入结束
else
InfixToSuffix(OPTR, s); //将中缀表达式转化为后缀表达式并输出
}
return 0;
}
算法步骤:
- 初始化栈:
- 初始化操作符栈
OPTR
和操作数栈OPND
。 - 操作符栈
OPTR
中最开始压入一个=
号作为起始符。
- 初始化操作符栈
- 扫描表达式:
- 从输入的表达式中逐个读取字符,称为
ch
。 - 如果
ch
不是操作符(即为数字),则将其压入操作数栈OPND
。
- 从输入的表达式中逐个读取字符,称为
- 处理操作符:
- 如果
ch
是操作符,则根据操作符栈栈顶元素与ch
的优先级比较结果,决定如何操作:- 优先级小于:当前操作符
ch
入操作符栈OPTR
。 - 优先级大于:弹出操作符栈顶的操作符,从操作数栈弹出两个操作数进行相应的运算,将运算结果压入操作数栈。
- 优先级等于:如果是左括号
(
和右括号)
配对,则弹出(
,匹配成功。
- 优先级小于:当前操作符
- 如果
- 表达式结束:
- 如果扫描到
=
或操作符栈顶为=
,则说明表达式处理结束。 - 操作数栈顶的值即为计算结果。
- 如果扫描到
- 后缀表达式转换:
- 当遇到数字时直接输出(相当于后缀表达式)。
- 遇到括号时处理优先级匹配。
- 最后输出栈中剩余的操作符(除了
=
号)。
第3关:基于栈的后缀算术表达式求值
任务描述
本关任务:从键盘上输入一个后缀表达式,试编写算法计算表达式的值。规定:后缀表达式的长度不超过一行,以“=”作为输入结束,操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。
编程要求
输入
多组数据,每组数据一行,对应一个后缀算术表达式,每个表达式均以“=”结尾。当表达式只有一个“=”时,输入结束。
输出
对于每组数据输出一行,为表达式的运算结果。
测试说明
平台会对你编写的代码进行测试:
测试输入:
1 2+8 2-7 4-/*=
1 2+=
1 2/=
=
预期输出:
6.00
3.00
0.50
#include <iostream>
#include<iomanip>
#include <string>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
using namespace std;
typedef struct
{//操作数栈
double* base;
double* top;
int stacksize;
}SqStack;
Status InitStack(SqStack& S)
{//操作数栈初始化
S.base = new double[MAXSIZE];
if (!S.base)
return ERROR;
S.top = S.base;
S.stacksize = MAXSIZE;
return OK;
}
Status Push(SqStack& S, double e)
{//操作数栈入栈
if (S.top - S.base >= S.stacksize)
return OVERFLOW;
*S.top++ = e;
return OK;
}
Status Pop(SqStack& S)
{//操作数栈出栈
if (S.top == S.base)
return ERROR;
S.top--;
return OK;
}
double GetTop(SqStack S)
{//操作数栈取栈顶元素
if (S.top == S.base)
return ERROR;
return *(S.top - 1);
}
double Calculate(double a, char op, double b)
{//计算表达式“a op b”的值
switch (op)
{
case '+':return a + b;
case '-':return a - b;
case '*':return a * b;
case '/':return a / b;
}
}
double EvaluateExpression(SqStack OPND, char s[])
{//后缀算术表达式求值
//设OPND为操作数栈
//表达式求值算法调用Calculate函数
char* ch = s;
double a;
double b;
double temp;
while (*ch != '=') {
if (*ch >= '0' && *ch <= '9') {//如果是数字,直接入栈
temp = *ch - '0';
Push(OPND, temp);
ch++;
}
else if (*ch == ' ') {//如果是空格,直接跳过
ch++;
}
else {//如果是运算符,则弹出两个数字进行相应运算
b = GetTop(OPND);//注意先弹出的实际上在表达式中靠后(影响-/)
Pop(OPND);
a = GetTop(OPND);
Pop(OPND);
temp = Calculate(a, *ch, b);
Push(OPND, temp);
ch++;
}
}
return GetTop(OPND);
}
int main()
{
char s[100];
//用字符数组存储表达式,每个数组元素仅存一个字符
while (1)
{
cin.getline(s, 100); //输入一行含空格的后缀表达式
if (s[0] == '=')
break; //当表达式只有一个"="时,输入结束
SqStack OPND;
InitStack(OPND); //初始化数字栈
cout << fixed << setprecision(2) << EvaluateExpression(OPND, s) << fixed << setprecision(2) << endl;
}
return 0;
}
算法步骤:
- 初始化栈:
- 初始化操作数栈
OPND
。
- 初始化操作数栈
- 扫描表达式:
- 从输入的表达式中逐个读取字符,称为
ch
。 - 如果
ch
是数字,则将其压入操作数栈OPND
。
- 从输入的表达式中逐个读取字符,称为
- 处理操作符:
- 如果
ch
是操作符,则从OPND中弹出两个操作数,进行相应运算(注意先弹出的是后一个操作数b)。再将计算结果重新压入栈。
- 如果
- 表达式结束:
- 如果扫描到
=
或操作符栈顶为=
,则说明表达式处理结束。 - 操作数栈顶的值即为计算结果,返回计算结果。
- 如果扫描到