C++——算术表达式的求值(数据结构课程设计)

数据结构课程设计——算术表达式的求值

1.实验目的

1.在课程设计中提高学生的动手能力和编程能力;
2.在课程设计中提高数据结构中理论知识(栈和二叉树等知识)的应用。
3.在课程设计中提高自己对各个方面知识的综合能力。

2.实验内容

一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正实数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“运算符优先法”求算术表达式的值。

3.实验原理

1.设计建立二叉树的头文件(BiTree.h);
2.设计程序中需要用到的栈的相关头文件(Stack.h);
3.设计一个函数去判断符号的优先级(StrPriority());
4.设计函数去判断是否输入的字符是否为运算符或者界符(Is_Operator());
5.通过输入的字符串数组去建立表达式树(InitExpTree());
6.设计一个函数去实现运算(GetStrValue());
7.设计一个函数去将输入的数字型的字符串转换成Double型(ToNumber());
8.设计一个函数去实现通过二叉树遍历进行运算结果求值(EvalateExpTree());
9.为了保证程序的健壮性，根据可能的错误可能性全部错误结果进行打印错误类型(ErrorTest());
10.为了判断是否要打印最终的结果，定义了一个标志Is_Success去进行判断。

4.实验设备

Win10计算机一台

5.实验要求

（1） 从键盘或文件读入一个合法的算术表达式，输出正确的结果。
（2） 显示输入序列和栈的变化过程。
（3） 考虑算法的健壮性，当表达式错误时，要给出错误原因的提示。

6.实验程序

1.创建二叉树的头文件(BiTree.h)

#pragma once
#include <string>
using namespace std;
typedef struct BiTNode
{
	char opstr;	     //结点符号域
	string number;	//结点数据域
	BiTNode *lchild, *rchild;	//左右孩子指针
}BiTNode,*BiTree;
void CreateExpTree_Op(BiTree &T, BiTree a, BiTree b, char theta)//a是左孩子，b是右孩子,theta是符号域
{
	BiTree L = new BiTNode;
	L->opstr = theta;
	L->lchild = a;
	L->rchild = b;
	T = L;
}

void CreateExpTree_Number(BiTree &T, BiTree a, BiTree b, string theta)//a是左孩子，b是右孩子,theta是数字域
{
	BiTree L = new BiTNode;
	L->number = theta;
	L->lchild = a;
	L->rchild = b;
	T = L;
}

2.用于建立栈的头文件(Stack.h)

#pragma once
#include"BiTree.h"
#include"Stack.h"
typedef struct StackNode
{
	BiTree Tree;	//存储的是二叉树
	char Operator;	//存储的是符号
	StackNode *next;
}StackNode,*LinkStack;
 
int InitStack(LinkStack &S)  //栈的初始化
{
	S = NULL;
	return 1;
}

int Push_EXPT(LinkStack &S, BiTree e) //二叉树入栈
{
	LinkStack p = new StackNode;
	p->Tree = e;
	p->next = S;
	S = p;
	return 1;
}

int Push_OPTR(LinkStack &S, char e) //运算符入栈
{
	LinkStack p = new StackNode;
	p->Operator = e;
	p->next = S;
	S = p;
	return 1;
}

int Pop_EXPT(LinkStack &S, BiTree &T1) //二叉树出栈
{
	if (S == NULL)	return 0;
	LinkStack p = S;
	T1 = p->Tree;
	S = S->next;
	delete p;
	return 1;
}

int Pop_OPTR(LinkStack &S, char &ch) //运算符出栈
{
	if (S == NULL)	return 0;
	LinkStack p = S;
	ch = p->Operator;
	S = S->next;
	delete p;
	return 1;
}

char GetTop_OPTR(LinkStack S)//取栈顶符号
{
	if (S != NULL)	return S->Operator;
	else return ' ';
}

BiTree GetTop_EXPT(LinkStack S) //取栈顶树
{
	if (S != NULL)	return S->Tree;
	else return NULL;
}

3.主函数(CountingStr.cpp)

#include <iostream>
#include <string>
#include <cmath>
#include"BiTree.h"
#include"Stack.h"
using namespace std;
bool Is_Success = true;  //成功标志
int OpArrayLength = 1;  //定义输入数组的长度
char StrPriority(char top, char ch)  //判断符号的优先级
{
	if (ch == ')'&&top == '(')	return '=';
	else if (ch == ')')	return '>';
	else if (top == ' ' || top == '(' || ch == '(') return '<';
	else if (ch == '#')	return '>';
	else if (top == '+' || top == '-')
	{
	if (ch == '+' || ch == '-')    return '>';
	else if (ch == '/' || ch == '*')	return '<';
	else return '0';
	}
	else if (top == '*' || top == '/')    return '>';
	else return '0';
}

void InitExpTree(char *str, LinkStack &EXPT, LinkStack &OPTR)    //创建树
{
	//int n = strlen(str);
	int n = OpArrayLength;                //求出有效长度
	BiTree T = NULL, T_left = NULL, T_right = NULL;	
	                               //T,T_left和T_right分别为根结点，左孩子，右孩子
	char ch;	                   //记录弹出的符号
	string number;	               //记录弹出来的数字
	int i = 1;
	while (i<n)        //没扫描到最后就一直循环 &&str[i]!='#'
	{
		if (str[i] >= '0' && str[i] <= '9') 
		{//如果它是数字，执行下列语句
			number += str[i]; 
			if (str[i + 1] >= '0' && str[i + 1] <= '9') 
			{	                             //下一位仍是数字则连接在一起
				i++;
				continue;
			}
			CreateExpTree_Number(T, NULL, NULL, number);  //创建只有一个元素的二叉树
			number = "";	               //建完数值的二叉树后number置空
			Push_EXPT(EXPT, T);
			if(T->number!="")cout << T->number << "已出EXPT栈" << endl;
			i++;
		}
		else                //如果它是符号，执行下列语句
		{
			switch (StrPriority(GetTop_OPTR(OPTR), str[i]))		//比较优先级
			{
			case '<':
				Push_OPTR(OPTR, str[i]);
				cout << str[i] << "已入OPTR栈" << endl;
				i++;
				break;
			case '>':+
				Pop_OPTR(OPTR, ch);	                //弹出OPTR栈顶
				if(ch!=' ') cout << ch << " 已出OPTR栈!" << endl;
				Pop_EXPT(EXPT, T_left);	       //弹出两个操作数
				if (T_left->number != "") cout << T_left->number << " 已出EXPT栈!" << endl;
				Pop_EXPT(EXPT, T_right);
				if (T_right->number != "") cout << T_right->number << " 已出EXPT栈" << endl;
				CreateExpTree_Op(T, T_right, T_left, ch);	//建立树
				Push_EXPT(EXPT, T);		      //最后把T放进EXPT栈中
				if (T->number != "") cout << T->number << " 已入EXPT栈" << endl;
				break;
			case '=':
				Pop_OPTR(OPTR, ch);
				if(ch!=' ') cout << ch << " 已出OPTR栈" << endl;
				i++;
				break;
			default:
				break;
			}
		}
	}
}

double GetStrValue(char data, double lvalue, double rvalue) //计算表达式的值 
{
	switch (data)
	{
	case '+':
		return lvalue + rvalue;
		break;
	case '-':
		return lvalue - rvalue;
		break;
	case '*':
		return lvalue * rvalue;
		break;
	case '/':
		return lvalue / rvalue; break;
	default: Is_Success = false;
		break;
	}
}

double ToNumber(string str)  //把string字符转换成数值
{
	int n = str.length(), m = str.length();
	double sum = 0;


	for (int i = 0; i < n; i++)
	{
		sum += (str[i] - '0') * pow(10, m - 1);
		m--;
	}
	return sum;
}

double EvaluateExpTree(BiTree T) //遍历表达式树求表达式的值
{
	double lvalue = 0, rvalue = 0;	  //存放叶子结点的数据域
	if (!T->lchild&& !T->rchild)
		return ToNumber(T->number);	  //转换为数字
	else {
		lvalue = EvaluateExpTree(T->lchild);	
		rvalue = EvaluateExpTree(T->rchild);
		return GetStrValue(T->opstr, lvalue, rvalue);
	}
}

void ErrorTest(char *str1)           //错误判断
{
	int j = 1; int left = 0, right = 0;
	bool wrong_flag = false;
	while (str1[j]!='#')         //扫描有么有异常符号
	{	
		char t = str1[j];
		if (t != '+'&&t != '-'&&t != '*'&&t != '/'&&t != '#'&&t!='('&&t!=')'&&!(t<='9'&&t>='0'))
		{
			Is_Success = false;
			cout << str1[j] << "符号输入错误！" << endl;
			wrong_flag = true;
			break;
		}
			j++;

	}
    j = 1;                      //重置为1
	if (!wrong_flag)
	{
		while (str1[j] != '#')
		{
			if (str1[j] == '(') left++;
			if (str1[j] == ')') right++;
			if (str1[j] == ')'&&str1[j + 1] == '(')
			{
				Is_Success = false;
				cout << str1[j] << str1[j + 1] << "处括号匹配失败！" << endl;
			}
			if ((str1[j] == '+' || str1[j] == '-' || str1[j] == '/' || str1[j] == '*') && str1[j + 1] == ')')
			{
				Is_Success = false;
				cout << str1[j] << str1[j + 1] << "处出现错误！" << endl;
			}
			if ((str1[j + 1] == '+' || str1[j + 1] == '-' || str1[j + 1] == '/' || str1[j + 1] == '*') && str1[j] == '(')
			{
				Is_Success = false;
				cout << str1[j] << str1[j + 1] << "处出现错误！" << endl;
			}
			if ((str1[j] == '+' || str1[j] == '-' || str1[j] == '*' || str1[j] == '/') &&
				(str1[j + 1] == '+' || str1[j + 1] == '-' || str1[j + 1] == '*' || str1[j + 1] == '/'))
			{
				cout << str1[j] << str1[j + 1] << "处运算符不能连续输入！" << endl;
				Is_Success = false;
			}
			j++;
		}
		j = 1;    //重置为1
		if (left != right)
		{
			Is_Success = false;
			cout << "括号数量匹配失败！" << endl;
		}
	}
	
}

void MainRun(LinkStack EXPT,LinkStack OPTR,BiTree T,char *OpArray)
{
	if (Is_Success)
	{
		InitExpTree(OpArray, EXPT, OPTR);	//构建表达式树
		Pop_EXPT(EXPT, T);
		cout << endl;
		int i = 1;      //用于后续遍历
		cout << "The result of ";
		while (OpArray[i] != '#')
		{
			cout << OpArray[i];
			i++;
		}
		cout << " is: " << EvaluateExpTree(T) << endl;	//求值结果
	}
}
int main()
{
	BiTree T = NULL; LinkStack EXPT; LinkStack OPTR;
	InitStack(EXPT);InitStack(OPTR);	
	//char OpArray[]= "#(7+15)*(23-28/4)#";//默认
	char OpArray[100];        //定义表达式数组
	int j=1;                   //计数器用来循环输入
	cout << "请输入表达式：";
	cin >> OpArray[0];
	if (OpArray[0] != '#') { cout << "请以#开始输入！" << endl; }
	else
	{
		cin >> OpArray[1]; OpArrayLength++; 
		while (OpArray[j] != '#')
		{
			cin >> OpArray[++j];
			OpArrayLength++;
	    }
		ErrorTest(OpArray);
		MainRun(EXPT, OPTR, T, OpArray);
	}
	system("pause");
}

4.运行结果

7.实验总结

1.通过课程设计中不断的查找相关资料，提高了自己对陌生知识的理解和掌握。
2.课程设计中大量用到了栈，增强自己对栈的相关知识的理解和应用。
3.提高了自己对程序健壮性判断的重要性，如果没有对错误进行判断，很容易出现编译器直接报错的情况。