IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 中缀表达式与前后缀表达式的相互转换、中缀表达式和前后缀表达式运算 -> 正文阅读

[数据结构与算法]中缀表达式与前后缀表达式的相互转换、中缀表达式和前后缀表达式运算

大一期末数据结构课设。

目的:表达式求值问题在程序设计中经常遇见,通过本课程设计,使学生掌握表达式的不同表示形式及相应的求值方法,加深对栈的基本原理和方法的理解和应用,培养学生运用语言编程及调试的能力,运用数据结构解决简单的实际问题的能力,为后续计算机专业课程的学习打下坚实的基础。

假定:表达式中的操作数皆为实数。运算符为:+、-、*、/、^(幂运算)等二元运算符。

要求

①?交互输入或从文本文件输入中缀表达式,解析表达式的合法性;

②?直接从中缀表达式求值;

③?将中缀表达式转换为后缀表达式;

④?后缀表达式求值;

⑤?将中缀表达式转换为前缀表达式;

⑥?前缀表达式求值;

学习了很多别的博客的算法思想,自己总结以后归纳了一下。

头文件放这了,没啥好说的。?

首先是栈的操作,比较基本

定义两个栈,因为涉及到运算符与数字的运算以及相互转换,所以两个栈分别为字符型和浮点型。

具体的后面的注释也比较详细了,就不详述了,每一个题目都拿符号分隔开了比较好找。

转换思想可以查查很多大佬的博客,代码思想就是栈转换的方法,手工的话个人非常喜欢树的转换,感觉可以将栈与树结合起来非常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;
}

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-07-14 23:11:55  更:2021-07-14 23:12:10 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年12日历 -2024/12/27 10:23:57-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码
数据统计