|
大一期末数据结构课设。
目的：表达式求值问题在程序设计中经常遇见，通过本课程设计，使学生掌握表达式的不同表示形式及相应的求值方法，加深对栈的基本原理和方法的理解和应用，培养学生运用语言编程及调试的能力，运用数据结构解决简单的实际问题的能力，为后续计算机专业课程的学习打下坚实的基础。
假定：表达式中的操作数皆为实数。运算符为：+、-、*、/、^（幂运算）等二元运算符。
要求：
①?交互输入或从文本文件输入中缀表达式，解析表达式的合法性；
②?直接从中缀表达式求值；
③?将中缀表达式转换为后缀表达式；
④?后缀表达式求值；
⑤?将中缀表达式转换为前缀表达式；
⑥?前缀表达式求值；
学习了很多别的博客的算法思想，自己总结以后归纳了一下。
头文件放这了，没啥好说的。?
首先是栈的操作，比较基本
定义两个栈，因为涉及到运算符与数字的运算以及相互转换，所以两个栈分别为字符型和浮点型。
具体的后面的注释也比较详细了，就不详述了，每一个题目都拿符号分隔开了比较好找。
转换思想可以查查很多大佬的博客，代码思想就是栈转换的方法，手工的话个人非常喜欢树的转换，感觉可以将栈与树结合起来非常nb。
下面是算法函数，主函数放后面了。虽说是cpp，但主题风格还是C。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#define Stack_Size 50
#define INF 21000000
using namespace std;
/***********************栈的基本操作*************************/
/*运算符之间的优先级制作成一张表格
+ - * / ( ) ^ #
+ > > < < < > < >
- > > < < < > < >
* > > > > < > < >
/ > > > > < > < >
( < < < < < = < 0
) > > > > 0 > > >
^ > > > > < > 0 >
# < < < < < 0 < =
*/
char cmp[][8]={
{'>', '>', '<', '<', '<', '>', '<', '>'},
{'>', '>', '<', '<', '<', '>', '<', '>'},
{'>', '>', '>', '>', '<', '>', '<', '>'},
{'>', '>', '>', '>', '<', '>', '<', '>'},
{'<', '<', '<', '<', '<', '=', '<', '0'},
{'>', '>', '>', '>', '0', '>', '>', '>'},
{'>', '>', '>', '>', '<', '>', '0', '>'},
{'<', '<', '<', '<', '<', '0', '<', '='} };
//定义运算符栈
typedef struct
{
char Elem[Stack_Size];
int top;
} Operator;
//定义数字栈
typedef struct
{
double Elem[Stack_Size];
int top;
} Number;
//初始化运算符栈
void InitStack_Operator(Operator* S)
{
S->top=-1;
}
//初始化数字栈
void InitStack_Number(Number* S)
{
S->top=-1;
}
//运算符栈出栈
int Pop_Operator(Operator* S)
{
if(S->top==-1){
printf("运算符栈为空\n");
system("Pause");
exit(10);
}
S->top--;
return 1;
}
//数字栈出栈
int Pop_Number(Number* S)
{
if(S->top==-1){
printf("数字栈为空\n");
system("Pause");
exit(11);
}
S->top--;
return 1;
}
//运算符栈入栈
int Push_Operator(Operator* S,char ch)
{
if(S->top==Stack_Size-1){
printf("运算符栈满\n");
system("Pause");
exit(12);
}
S->top++;
S->Elem[S->top]=ch;
return 1;
}
//数字栈入栈
int Push_Number(Number* S,double ch)
{
if(S->top==Stack_Size-1){
printf("运算符栈满\n");
system("Pause");
exit(13);
}
S->top ++;
S->Elem[S->top]=ch;
return 1;
}
//取运算符栈栈顶元素
char Gettop_Operator(Operator *S)
{
if(S->top==-1){
printf("运算符栈为空\n");
system("Pause");
exit(17);
}
return S->Elem[S->top];
}
//取数字栈栈顶元素
double Gettop_Number(Number *S)
{
if(S->top==-1){
printf("数字栈为空\n");
system("Pause");
exit(18);
}
return S->Elem[S->top];
}
/*****************实现中缀表达式运算****************/
//进行两个数字间的运算
double Calc(double a,double b,char opt)
{
double res;
if (opt == '+') //加法运算
res = a + b;
if (opt == '-') //减法运算
res = a - b;
if (opt == '*') //乘法运算
res = a * b;
if (opt == '/'){ //除法运算
if(fabs(b) < 1e-6){ //检查是否出现除0现象
printf("发生除0错误\n");
system("Pause");
exit(15);
}
res = a / b;
}
if (opt == '^') //乘方运算
res = pow(a, b);
printf("%.2lf %c %.2lf = %.2lf\n", a, opt, b, res);
return res;
}
//比较运算符优先级
int change(char ch)
{
switch(ch){ //返回运算符在运算符关系表中的位置
case '+':
return 0;
case '-':
return 1;
case '*':
return 2;
case '/':
return 3;
case '(':
return 4;
case ')':
return 5;
case '^':
return 6;
case '#':
return 7;
}
return -INF;
}
//比较运算符大小
char compare(char a,char b)
{
if(cmp[change(a)][change(b)] == '0'){
printf("表达式错误\n");
system("Pause");
exit(16);
}
return cmp[change(a)][change(b)];
}
//检验函数有无其他符号
bool check(char *s,int len)
{
for(int i=0; i<len; i++){
if(s[i] >= '0' && s[i] <= '9') continue;
if(s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '.') continue;
if(s[i] == '/' || s[i] == '(' || s[i] == ')' || s[i] == '^') continue;
return false;
}
return true;
}
double getResult(char *a)
{
char b[10]; //定义一个数组用于存放数字,方便char向double类型的转换
int len = strlen(a); //获得表达式长度
Operator signs;
Number number;
InitStack_Number(&number); //初始化栈
InitStack_Operator(&signs);
Push_Operator(&signs,'#'); //将表达式开头标志入栈
double x, y;
if (!check(a, len)){ //检查是否有多余字符
printf("输入中存在多余字符\n");
system("Pause");
exit(19);
}
a[len] = '#'; //设置表达式结束标志
int i; //i用于遍历表达式
bool f = false; //用f当作读完一个数字长度标志,比如12.34,当读完4后才继续读运算符
int k = 0; //用于存放数字的长度,即数组b的数据长度
for (i = 0; i <= len; i++){
if ((a[i] >= '0' && a[i] <= '9') || a[i] == '.'){ //将数字读入数组b
b[k++] = a[i];
f = true;
continue;
}
if (f){
b[k]='\0';
Push_Number(&number, atof(b)); //将数组b内全部数字以及小数点转化成浮点型数字存入数字栈
f = false;
k = 0;
}
switch(compare(Gettop_Operator(&signs), a[i])){ //比较当前运算符和运算符栈顶运算符优先级
case '<':
Push_Operator(&signs,a[i]); //优先级低则入栈,不运算
break;
case'=':
Pop_Operator(&signs); //优先级相等则表明是左右括号或者两个定界符#
break;
case'>':
y = Gettop_Number(&number); //取栈顶数字
Pop_Number(&number); //数字出栈
x = Gettop_Number(&number);
Pop_Number(&number);
Push_Number(&number,Calc(x,y,Gettop_Operator(&signs))); //将数字与运算符进行运算
Pop_Operator(&signs); //运算结束后运算符出栈
i--; //运算后从运算结果开始继续运算
break;
}
}
double ans = Gettop_Number(&number); //取最终运算结果
return ans;
}
/**********************从文件读入表达式运算********************/
double readFile(char *fileName)
{
FILE *fp; //文件指针
char str[Stack_Size];
fp = fopen(fileName, "r");
if (fp == NULL){
cout << "文件打开失败!" << endl;
system("Pause");
return -INF;
}
fgets(str, Stack_Size, fp);
return getResult(str);
}
/**********************中缀表达式转后缀表达式********************/
void suffixChange(char *str)
{
int len = 0;
char comp;
Operator NUM, SIGN;
InitStack_Operator(&NUM); //初始化栈
InitStack_Operator(&SIGN);
while (*(str + len) != '\0'){
if (str[len] >= '0' && str[len] <= '9') //如果是操作数则直接入栈
Push_Operator(&NUM, str[len]);
else { //如果是操作符;
if (SIGN.top == -1) //符号栈空则直接入栈
Push_Operator(&SIGN, str[len]);
else if (Gettop_Operator(&SIGN) == '(') //符号栈顶元素为左括号，直接将操作符放入符号栈中
Push_Operator(&SIGN, str[len]);
else if (str[len] == '(') //如果遇到左括号，直接将左括号放入符号栈中
Push_Operator(&SIGN, str[len]);
else {
if (str[len] == ')'){ //如果遇到右括号，将左括号到右括号之间的全部符号移出到NUM中
while (Gettop_Operator(&SIGN) != '('){
Push_Operator(&NUM, Gettop_Operator(&SIGN));
Pop_Operator(&SIGN);
}
Pop_Operator(&SIGN); //将左括号出栈
}
else { //如果当前栈顶元素的优先级大于操作数的优先级，则将栈顶元素出栈到数字栈中，再次和判断出栈后
//栈的栈顶元素比较优先级大小，直到当前栈顶元素小于操作数优先级，将操作符放入符号栈中
comp = compare(str[len], Gettop_Operator(&SIGN));
while (comp != '>'){
Push_Operator(&NUM, Gettop_Operator(&SIGN)); //将符号栈顶元素压入数字栈
Pop_Operator(&SIGN); //符号栈退栈
if (SIGN.top != -1)
comp = compare(str[len], Gettop_Operator(&SIGN)); //符号栈非空则比较先后顺序,符号栈空则直接压栈
else
break;
}
Push_Operator(&SIGN, str[len]); //压栈
}
}
}
len++;
}
Operator T;
InitStack_Operator(&T);
while (SIGN.top != -1){
Push_Operator(&NUM, Gettop_Operator(&SIGN));
Pop_Operator(&SIGN);
}
cout << "转换后的后缀表达式为:" << endl;
while (NUM.top != -1){ //顺序出栈,此处可用队列代替,但由于未定义队列结构以及函数,故用暂存栈T代替
Push_Operator(&T, Gettop_Operator(&NUM));
Pop_Operator(&NUM);
}
while (T.top != -1){
cout << Gettop_Operator(&T) << " ";
Pop_Operator(&T);
}
}
/************************后缀表达式运算**************************/
bool GetOperands(Number *S, double *op1, double *op2)
{
*op1 = Gettop_Number(S);
Pop_Number(S);
*op2 = Gettop_Number(S);
Pop_Number(S);
return true;
}
void doSufOperator(Number *S, char ope)
{
bool result;
double ope1, ope2;
result = GetOperands(S, &ope1, &ope2);
if (result){
switch(ope){ //选择计算符号
case '+':
Push_Number(S, ope2 + ope1);
break;
case '-':
Push_Number(S, ope2 - ope1);
break;
case '*':
Push_Number(S, ope2 * ope1);
break;
case '/':
if(fabs(ope2)<1e-6){ //防止出现除数为0的错误
cout << "除数为0" << endl;
system("Pause");
exit(20);
}
else{
Push_Number(S, ope2 / ope1);
}
break;
case '^':
Push_Number(S, pow(ope2, ope1));
break;
}
cout << ope2 << " " << ope << " " << ope1 << " " << endl; //打印每一次的计算过程
}
}
void suffixOperate(void)
{
Number S;
InitStack_Number(&S);
char c[Stack_Size];
double newop;
cout << "请输入后缀表达式,以空格分开数字以及运算符,以输入#结尾" << endl;
int i;
for (i = 0; i < Stack_Size && c[i - 1] != '#'; i++){ //遍历输入,以#结尾是为了防止输入空格时未读入
cin >> c[i];
}
c[--i] = '\0'; //字符串结束标志
for(i = 0; c[i] != '\0'; i++){ //遍历字符串
switch(c[i])
{
case '+':
case '-':
case '*':
case '/':
case '^':
doSufOperator(&S, c[i]);
break;
case '_':
break;
default:
newop = c[i] - '0';
Push_Number(&S, newop);
}
}
cout << "运算结果为:" << endl;
cout << Gettop_Number(&S) << endl;
}
/**********************中缀表达式转前缀表达式***********************/
void prefixChange(char *str)
{
int len = 0;
while (*(str + len) != '\0') //从右向左开始遍历，记录表达式长度
len++;
len--;
char comp;
Operator NUM, SIGN;
InitStack_Operator(&NUM); //初始化栈
InitStack_Operator(&SIGN);
while (len >= 0){
if (str[len] >= '0' && str[len] <= '9') //如果是操作数则直接入栈
Push_Operator(&NUM, str[len]);
else { //如果是操作符;
if (SIGN.top == -1) //符号栈空则直接入栈
Push_Operator(&SIGN, str[len]);
else if (Gettop_Operator(&SIGN) == ')') //符号栈顶元素为右括号‘）’，直接将操作符放入符号栈中
Push_Operator(&SIGN, str[len]);
else if (str[len] == ')') //如果遇到右括号，直接将右括号放入符号栈中
Push_Operator(&SIGN, str[len]);
else {
if (str[len] == '('){ //如果遇到左括号，将右括号到左括号之间的全部符号移出到NUM 中
while (Gettop_Operator(&SIGN) != ')'){
Push_Operator(&NUM, Gettop_Operator(&SIGN));
Pop_Operator(&SIGN);
}
Pop_Operator(&SIGN); //将右括号出栈
}
else { //如果当前栈顶元素的优先级大于操作数的优先级，则将栈顶元素出栈到数字栈中，再次和判断出栈后
//栈的栈顶元素比较优先级大小，直到当前栈顶元素小于或等于操作数优先级，将操作符放入符号栈中
comp = compare(str[len], Gettop_Operator(&SIGN));
while (comp == '<'){
Push_Operator(&NUM, Gettop_Operator(&SIGN)); //将符号栈顶元素压入数字栈
Pop_Operator(&SIGN); //符号栈退栈
if (SIGN.top != -1)
comp = compare(str[len], Gettop_Operator(&SIGN)); //符号栈非空则比较先后顺序,符号栈空则直接压栈
else
break;
}
Push_Operator(&SIGN, str[len]); //压栈
}
}
}
len--;
}
while (SIGN.top != -1){
Push_Operator(&NUM, Gettop_Operator(&SIGN));
Pop_Operator(&SIGN);
}
cout << "转换后的前缀表达式为:" << endl;
while (NUM.top != -1){ //逆序输出表达式
cout << Gettop_Operator(&NUM) << " ";
Pop_Operator(&NUM);
}
}
/************************前缀表达式运算********************/
void doPreOperator(Number *S, char ope)
{
bool result;
double ope1, ope2;
result = GetOperands(S, &ope1, &ope2);
if (result){
switch(ope){
case '+':
Push_Number(S, ope1 + ope2);
break;
case '-':
Push_Number(S, ope1 - ope2);
break;
case '*':
Push_Number(S, ope1 * ope2);
break;
case '/':
if(fabs(ope2)<1e-6){ //判断除数是否为0
cout << "除数为0" << endl;
system("Pause");
exit(20);
}
else{
Push_Number(S, ope1 / ope2);
}
break;
case '^':
Push_Number(S, pow(ope1, ope2));
break;
}
cout << ope1 << " " << ope << " " << ope2 << " " << endl; //打印每一次计算过程
}
}
void prefixOperate(void)
{
Number S;
InitStack_Number(&S);
char c[Stack_Size];
double newop;
cout << "请输入前缀表达式,以空格分开数字以及运算符,以输入#结尾" << endl;
int i;
for (i = 0; i < Stack_Size && c[i - 1] != '#'; i++){ //遍历输入,以#结尾是为了防止输入空格时未读入
cin >> c[i];
}
i -= 2; //从#之前开始遍历
while(i >= 0){
switch(c[i])
{
case '+':
case '-':
case '*':
case '/':
case '^':
doPreOperator(&S, c[i]);
break;
case '_':
break;
default:
newop = c[i] - '0';
Push_Number(&S, newop);
}
i--;
}
cout << "运算结果为:" << endl;
cout << Gettop_Number(&S) << endl;
}
主函数
#ifndef _MAIN_H
#define _MAIN_H
#include "Algorithm.h"
#endif // _MAIN_H
int main(void)
{
/*附录:
测试用数据
1. 数据①: ((5-3)^3)/2+12.34
数据②: 5-8+2/0
数据③: 3-9^2?1
2. Operation.txt其中表达式为((5-3)^7)/2+2.66
3. 数据①: (8+3)*9/3-2^3
数据②: 1+2*(3-4)/5^6
4. 数据①: 8 3 + 9 3 / * 2 3 ^ - #所对应的中缀表达式为(8+3)*9/3-2^3
数据②: 1 2 8 4 3 + - * / #所对应的中缀表达式为1/(2*(8-(4+3)))
5. 数据①: (8+3)*9/3-2^3
数据②: 1+2*(3-4)/5^6
6. 数据①: - / * + 8 3 9 3 ^ 2 3 #所对应的中缀表达式为(8+3)*9/3-2^3
数据②: - + 1 * 3 2 4 #所对应的中缀表达式为1+3*2-4 */
int index;
while (1){
system("CLS");
cout << "**************************************" << endl;
cout << "********欢迎使用表达式运算系统********" << endl;
cout << "**************************************" << endl;
cout << "**1.由键盘输入交互进行进行表达式运算**" << endl;
cout << "**2.由文件读入进行表达式运算 **" << endl;
cout << "**3.将中缀表达式转换为后缀表达式 **" << endl;
cout << "**4.后缀表达式求值 **" << endl;
cout << "**5.将中缀表达式转换为前缀表达式 **" << endl;
cout << "**6.前缀表达式求值 **" << endl;
cout << "**0.退出程序 **" << endl;
cout << "**************************************" << endl;
cout << "--------------------------------------" << endl;
cout << "**************************************" << endl;
cin >> index;
switch (index){
case 1:
char str[Stack_Size];
system("CLS");
cout << "******************************" << endl;
cout << "****欢迎使用表达式运算系统****" << endl;
cout << "******************************" << endl << endl;
cout << "请输入数学表达式" << endl;
cin >> str;
cout << "运算所得的值为:" << getResult(str) << endl;
break;
case 2:
char fileName[100];
system("CLS");
cout << "******************************" << endl;
cout << "****欢迎使用表达式运算系统****" << endl;
cout << "******************************" << endl << endl;
cout << "请输入想要读取的文本文件" << endl;
cin >> fileName;
cout << "文本文件中表达式的值为" << readFile(fileName) << endl;
break;
case 3:
system("CLS");
cout << "******************************" << endl;
cout << "****欢迎使用表达式运算系统****" << endl;
cout << "******************************" << endl << endl;
char suf[Stack_Size];
cout << "请输入中缀表达式" << endl;
cin >> suf;
suffixChange(suf);
break;
case 4:
system("CLS");
cout << "******************************" << endl;
cout << "****欢迎使用表达式运算系统****" << endl;
cout << "******************************" << endl << endl;
suffixOperate();
break;
case 5:
char pre[Stack_Size];
system("CLS");
cout << "******************************" << endl;
cout << "****欢迎使用表达式运算系统****" << endl;
cout << "******************************" << endl << endl;
cout << "请输入中缀表达式" << endl;
cin >> pre;
prefixChange(pre);
break;
case 6:
system("CLS");
cout << "******************************" << endl;
cout << "****欢迎使用表达式运算系统****" << endl;
cout << "******************************" << endl << endl;
prefixOperate();
break;
case 0:
system("CLS");
cout << "******************************" << endl;
cout << "******感谢您的使用,再见!******" << endl;
cout << "******************************" << endl;
system("Pause");
exit(0);
default :
cout << "输入选项有误!" << endl;
break;
}
system("Pause");
}
return 0;
}
|