数据结构实验二-基于栈的算术表达式求值算法

第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;
}

算法步骤:

  1. 初始化栈
    • 初始化操作符栈 OPTR 和操作数栈 OPND
    • 操作符栈 OPTR 中最开始压入一个 = 号作为起始符。
  2. 扫描表达式
    • 从输入的表达式中逐个读取字符,称为 ch
    • 如果 ch 不是操作符(即为数字),则将其压入操作数栈 OPND
  3. 处理操作符
    • 如果 ch 是操作符,则根据操作符栈栈顶元素与 ch 的优先级比较结果,决定如何操作:
      • 优先级小于:当前操作符 ch 入操作符栈 OPTR
      • 优先级大于:弹出操作符栈顶的操作符,从操作数栈弹出两个操作数进行相应的运算,将运算结果压入操作数栈。
      • 优先级等于:如果是左括号 ( 和右括号 ) 配对,则弹出 (,匹配成功。
  4. 表达式结束
    • 如果扫描到 = 或操作符栈顶为 =,则说明表达式处理结束。
    • 操作数栈顶的值即为计算结果。
  5. 后缀表达式转换
    • 当遇到数字时直接输出(相当于后缀表达式)。
    • 遇到括号时处理优先级匹配。
    • 最后输出栈中剩余的操作符(除了 = 号)。

第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;
}

算法步骤:

  1. 初始化栈
    • 初始化操作数栈 OPND
  2. 扫描表达式
    • 从输入的表达式中逐个读取字符,称为 ch
    • 如果 ch 是数字,则将其压入操作数栈 OPND
  3. 处理操作符
    • 如果 ch 是操作符,则从OPND中弹出两个操作数,进行相应运算(注意先弹出的是后一个操作数b)。再将计算结果重新压入栈。
  4. 表达式结束
    • 如果扫描到 = 或操作符栈顶为 =,则说明表达式处理结束。
    • 操作数栈顶的值即为计算结果,返回计算结果。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇