栈：中缀表达式转后缀表达式(逆波兰式)求值（支持多位数）【C语言，数据结构】（内含源代码）

题目：

需求分析：

概要设计：

详细设计：

题目：

设计并验证以下算法：首先将一个中缀表达式转换成逆波兰式（后缀表达式），然后对此逆波兰表达式求值。

需求分析：

1.输入分析：可能输入正确的和错误的表达式，可能输入超过一位的数字，输入的表达式可能产生浮点类型的结果，输入中空格可能出现在任何地方，输入由‘#’结尾。（现只输入整数）

2.演示程序在用户输入完整表达式后，若表达式不合法则输出相应提示，先输出用户表达式，再输出逆波兰表达式，最后输出其结果。

3.程序执行命令包括：(1)接受输入 (2)判断输入 (3)求逆波兰式 (4)根据逆波兰式求值

4.测试数据：


1+1#
 
1+2*3-4/5#
 
(4+2)*3-3/2#
 
(4+2)*(8-2)/2#

概要设计：

1.输入数据可以用数组存储，或者用顺序表存储，在本次实验用数组存储。

2.判断与转换同时进行。数据处理部分，为了使程序更快，只用遍历一次原输入，所以在这里让判断正误与转逆波兰表达式同时进行。

3.使用两种栈。在表达式转逆波兰表达式的时候需要用到栈来存储操作符，并且在使用逆波兰式表达式求值的时候也要用到栈来存储数，所以用要用两种栈来存储不同的数据类型。

4.程序模块：

（1）主程序模块：


void main(){
    初始化
    接受输入
    判断与转换
    求值
    输出
    结束
}

详细设计：

1.跳过空格。输入的数据和符号在用户看来，为了美观可能会添加空格，所以在我们转逆波兰表达式的时候要跳过空格来处理字符。

2.空格隔开数。因为输入可能是多位数，在后缀表达式里，我们怎么区分一个数是否为多位数呢？我想到的方法是用空格来个开各个数，这样就能区分了。详细操作是，每当遇到操作符，代表上一个数已经遍历完毕，在表达式数组中存入空格，来分开数据。

3.转逆波兰表达式

算法是这样的，从头开始遍历输入，当遇到数，就直接存入顺序表中。遇到符号时，就进行特殊处理：

当栈内元素为空的时候，直接存入：

当栈内有元素的时候，特殊处理。具体为，栈内优先级低于该符号则存入栈内，栈内优先级高于该符号，则把栈内符号输出，继续比较栈内符号。（操作会直到栈内符号优先级高于它，或栈内为空的时候）：

括号特殊处理。可以看做'('的优先级高于一切， ')'时，输出栈内元素，直到栈内上一个'('。

遍历完所有后，清空栈内元素，当遍历完所有元素后，把栈内剩余的操作符全部出栈。

对，就是这么简单。


void GetPE(SqList L, SqList *PE) {
	//根据输入求后缀表达式，若输入错误则报错
	int f = 1;			//判断输入工具
	int l = L.length;
	SqStack OP;			//操作符栈
	char c;
	int s = 0;
	InitStack(&OP);
	if(L.elem[0] <= '9' && L.elem[0] >= '0') {
		f = 0;
	}
	for(int i = 0; i < l; i++) {
		if(L.elem[i] <= '9' && L.elem[i] >= '0') {
			f = 0;
			ListInsert_SqList(PE, -1, L.elem[i]);
		} else {
			if(L.elem[i] != '(' && L.elem[i] != ')') {
 
				if(i != 0 && f == 1) {
					printf("ERROR!");
					exit(ERROR);
				}
				f = 1;
			}
			if(L.elem[i] == '(') {
				Push(&OP, L.elem[i]);
			} else if(L.elem[i] == ')') {
				Pop(&OP, &c);
				while(c != '(') {
					ListInsert_SqList(PE, -1, c);
					Pop(&OP, &c);
				}
			} else if(L.elem[i] == '+' || L.elem[i] == '-') {
				s = GetTop(OP, &c);
				while(s != 0 && c != '(') {
					Pop(&OP, &c);
					ListInsert_SqList(PE, -1, c);
					s = GetTop(OP, &c);
				}
				Push(&OP, L.elem[i]);
			} else if(L.elem[i] == '/' || L.elem[i] == '*') {
				s = GetTop(OP, &c);
				while(s == 1 && (c == '*' || c == '/')) {
					Pop(&OP, &c);
					ListInsert_SqList(PE, -1, c);
					s = GetTop(OP, &c);
				}
				Push(&OP, L.elem[i]);
			}
			if(L.elem[i] != '(' && L.elem[i] != ')') {
				ListInsert_SqList(PE, -1, ' ');
			}
		}
	}
	s = GetTop(OP, &c);		//判断并输出栈中剩余符号
	while(s) {
		Pop(&OP, &c);
		ListInsert_SqList(PE, -1, c);
		s = GetTop(OP, &c);
	}
}

4.逆波兰表达式求值

逆波兰表达式的方法很简单，就是遇到符号就进行前两个数的计算，在入栈。

不会的推荐这一篇文章。

http://t.csdn.cn/yOqQN


float GetPEResult(SqList L) {
	//根据后缀表达式求结果
	float sum = 0, tool2;
	int tool, flag;
	int l = L.length;
	SqStack2 PR;			//数字栈
	InitStack2(&PR);
	for(int i = 0; i < l; i++) {
		tool = 0, flag = 0, tool2 = 0, sum = 0;
		while(L.elem[i] <= '9' && L.elem[i] >= '0') {
			tool = tool * 10;
			tool += L.elem[i] - '0';
			i++;
			flag = 1;
		}
		if(flag == 1) {
			Push2(&PR, (float)tool);
		}
		switch(L.elem[i]) {
		case '+':
			Pop2(&PR, &tool2);
			Pop2(&PR, &sum);
			Push2(&PR, tool2 + sum);
			break;
		case '-':
			Pop2(&PR, &tool2);
			Pop2(&PR, &sum);
			Push2(&PR, sum - tool2);
			break;
		case '*':
			Pop2(&PR, &tool2);
			Pop2(&PR, &sum);
			Push2(&PR, tool2 * sum);
			break;
		case '/':
			Pop2(&PR, &tool2);
			Pop2(&PR, &sum);
			Push2(&PR, sum / tool2);
			break;
		}
	}
	Pop2(&PR, &sum);
	return sum;
}

总结：

这个程序还可以简化，在转逆波兰的时候，用到了很多if语句，还可以把操作符的优先级做成一张表格，通过表格来进行判断。

用户手册：

1.本程序运行环境为DOS。

2.输入表达式后#结束，回车

3.根据输入，程序输出逆波兰表达式与结果。

测试结果：

源代码：

主程序：


#include "head.h"
 
void Input(SqList * );	//把输入进行特殊处理后存入，#结束
void GetPE(SqList, SqList *);	//根据输入求后缀表达式，若输入错误则报错
float GetPEResult(SqList);	//根据后缀表达式求结果
 
int main() {
	float answer;
	SqList input, PE;		//初始化
	InitList_SqList(&input);
	InitList_SqList(&PE);
 
	printf("Please enter your expression and end with '#':\n");
	Input(&input);	//把输入存入input中
 
	printf("Your input is: ");	//输出原式
	printlist_SqList(input);
 
	GetPE(input, &PE);	//输出逆波兰式
	printf("To RPExpression is: ");
	printlist_SqList(PE);
 
	answer = GetPEResult(PE);
	printf("Answer is: %.2lf", answer);
 
	return 0;
}
 
void Input(SqList *input) {
	//把输入进行特殊处理后存入，#结束
	ElemType c;
	while(1) {
		scanf(" %c", &c);
		if(c == '#') {
			break;
		}
		ListInsert_SqList(input, -1, c);
	}
}
 
void GetPE(SqList L, SqList *PE) {
	//根据输入求后缀表达式，若输入错误则报错
	int f = 1;			//判断输入工具
	int l = L.length;
	SqStack OP;			//操作符栈
	char c;
	int s = 0;
	InitStack(&OP);
	if(L.elem[0] <= '9' && L.elem[0] >= '0') {
		f = 0;
	}
	for(int i = 0; i < l; i++) {
		if(L.elem[i] <= '9' && L.elem[i] >= '0') {
			f = 0;
			ListInsert_SqList(PE, -1, L.elem[i]);
		} else {
			if(L.elem[i] != '(' && L.elem[i] != ')') {
 
				if(i != 0 && f == 1) {
					printf("ERROR!");
					exit(ERROR);
				}
				f = 1;
			}
			if(L.elem[i] == '(') {
				Push(&OP, L.elem[i]);
			} else if(L.elem[i] == ')') {
				Pop(&OP, &c);
				while(c != '(') {
					ListInsert_SqList(PE, -1, c);
					Pop(&OP, &c);
				}
			} else if(L.elem[i] == '+' || L.elem[i] == '-') {
				s = GetTop(OP, &c);
				while(s != 0 && c != '(') {
					Pop(&OP, &c);
					ListInsert_SqList(PE, -1, c);
					s = GetTop(OP, &c);
				}
				Push(&OP, L.elem[i]);
			} else if(L.elem[i] == '/' || L.elem[i] == '*') {
				s = GetTop(OP, &c);
				while(s == 1 && (c == '*' || c == '/')) {
					Pop(&OP, &c);
					ListInsert_SqList(PE, -1, c);
					s = GetTop(OP, &c);
				}
				Push(&OP, L.elem[i]);
			}
			if(L.elem[i] != '(' && L.elem[i] != ')') {
				ListInsert_SqList(PE, -1, ' ');
			}
		}
	}
	s = GetTop(OP, &c);		//判断并输出栈中剩余符号
	while(s) {
		Pop(&OP, &c);
		ListInsert_SqList(PE, -1, c);
		s = GetTop(OP, &c);
	}
}
float GetPEResult(SqList L) {
	//根据后缀表达式求结果
	float sum = 0, tool2;
	int tool, flag;
	int l = L.length;
	SqStack2 PR;			//数字栈
	InitStack2(&PR);
	for(int i = 0; i < l; i++) {
		tool = 0, flag = 0, tool2 = 0, sum = 0;
		while(L.elem[i] <= '9' && L.elem[i] >= '0') {
			tool = tool * 10;
			tool += L.elem[i] - '0';
			i++;
			flag = 1;
		}
		if(flag == 1) {
			Push2(&PR, (float)tool);
		}
		switch(L.elem[i]) {
		case '+':
			Pop2(&PR, &tool2);
			Pop2(&PR, &sum);
			Push2(&PR, tool2 + sum);
			break;
		case '-':
			Pop2(&PR, &tool2);
			Pop2(&PR, &sum);
			Push2(&PR, sum - tool2);
			break;
		case '*':
			Pop2(&PR, &tool2);
			Pop2(&PR, &sum);
			Push2(&PR, tool2 * sum);
			break;
		case '/':
			Pop2(&PR, &tool2);
			Pop2(&PR, &sum);
			Push2(&PR, sum / tool2);
			break;
		}
	}
	Pop2(&PR, &sum);
	return sum;
}

头文件：


#include  			//头文件
#include 
#include 
#include 
#include 
 
#define TRUE 1	//函数结果状态码
#define FALSE 0
#define ERROR 0
#define OK 1
#define EQUAL 1
#define OVERFLOW -1
#define INFEASIBLE -2
#define STACK_INIT_SIZE 100	//存储空间初始分配量
#define STACKINCREMENT 10	//存储空间分配增量
#define LIST_INIT_SIZE 100	//顺序表存储空间的初始分配量
#define LISTINCREMENT 10	//顺序表存储空间的分配增量
 
typedef int Status;	//Status 为函数返回值类型，其值为函数结果状态代码
 
typedef char SElemType;	//栈中数据元素类型为char型
typedef float SElemType2;	//栈中数据元素类型为float型
 
typedef struct {	//栈的顺序存储表示
	SElemType* base;	//栈构造之前和销毁之后，其值为NULL
	SElemType* top;	//栈顶指针
	int stacksize;	//当前已分配的存储空间
} SqStack;
 
typedef struct {	//栈的顺序存储表示
	SElemType2* base;	//栈构造之前和销毁之后，其值为NULL
	SElemType2* top;	//栈顶指针
	int stacksize;	//当前已分配的存储空间
} SqStack2;
 
typedef char ElemType;//顺序表中数据元素类型
 
struct LIST {
	ElemType* elem;			//顺序表的存储空间基址
	int length;				//当前长度
	int listsize;			//当前分配的存储容量
};
typedef struct LIST SqList;	//线性表的顺序存储结构定义
 
Status InitStack(SqStack*);			//栈初始化
Status DestroyStack(SqStack*);		//销毁栈
Status StackEmpty(SqStack);			//栈判空
Status GetTop(SqStack, SElemType*);	//取栈顶元素
Status Push(SqStack*, SElemType);	//入栈
Status Pop(SqStack*, SElemType*);	//出栈
Status StackTraverse(SqStack);		//遍历栈，输出每个数据元素
Status InitList_SqList(SqList*);	//构造一张新的顺序表L
Status ListInsert_SqList(SqList*, int, ElemType );	//在顺序表L的第i个元素前插入新元素e
int ListLength_SqList(SqList);		//求顺序表L的长度
Status Destroy_SqList(SqList*);		//销毁一张顺序表
void printlist_SqList(SqList);		//输出顺序表
Status InitStack2(SqStack2*);			//栈初始化
Status DestroyStack2(SqStack2*);		//销毁栈
Status StackEmpty2(SqStack2);			//栈判空
Status GetTop2(SqStack2, SElemType2*);	//取栈顶元素
Status Push2(SqStack2*, SElemType2);	//入栈
Status Pop2(SqStack2*, SElemType2*);	//出栈
Status StackTraverse2(SqStack2);		//遍历栈，输出每个数据元素
 
Status InitStack(SqStack* S) {
	//构造一个空栈Ss
	S->base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
	if(!S->base) {
		//存储分配失败
		exit(OVERFLOW);
	}
	S->top = S->base;
	S->stacksize = STACK_INIT_SIZE;
	return OK;
}//InitStack
 
Status GetTop(SqStack S, SElemType* e) {
	//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
	if(S.top == S.base) {
		return ERROR;
	}
	*e = *(S.top - 1);
	return OK;
}//GetTop
 
Status Push(SqStack* S, SElemType e) {
	//插入元素e为新的栈顶元素
	if(S->top - S->base >= S->stacksize) {
		//栈满，追加存储空间
		S->base = (SElemType*)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(SElemType));
		if(!S->base) {
			//存储分配失败
			exit(OVERFLOW);
		}
		S->top = S->base + S->stacksize;
		S->stacksize += STACKINCREMENT;
	}
	*S->top++ = e;
	return OK;
}//Push
 
Status Pop(SqStack* S, SElemType* e) {
	//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROE
	if(S->top == S->base) {
		return ERROR;
	}
	*e = *(--S->top);
	return OK;
}//Pop
 
Status DestoryStack(SqStack* S) {
	//销毁栈S
	if(S->base) {
		free(S->base);
	}
	S->top = S->base = NULL;
	return OK;
}//DestroyStack
 
Status StackTraverse(SqStack S) {
	//遍历栈，输出每一个数据元素
	SElemType* p = S.base;
	int i = 0;
	if(S.base == S.top) {
		printf("Stack is Empty.\n");
		return OK;
	}
	while(p < S.top) {
		printf("[%d:%c]", ++i, *p++);
	}
	printf("\n");
	return OK;
}//StackTraverse
 
Status InitStack2(SqStack2* S) {
	//构造一个空栈Ss
	S->base = (SElemType2*)malloc(STACK_INIT_SIZE * sizeof(SElemType2));
	if(!S->base) {
		//存储分配失败
		exit(OVERFLOW);
	}
	S->top = S->base;
	S->stacksize = STACK_INIT_SIZE;
	return OK;
}//InitStack
 
Status GetTop2(SqStack2 S, SElemType2* e) {
	//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
	if(S.top == S.base) {
		return ERROR;
	}
	*e = *(S.top - 1);
	return OK;
}//GetTop
 
Status Push2(SqStack2* S, SElemType2 e) {
	//插入元素e为新的栈顶元素
	if(S->top - S->base >= S->stacksize) {
		//栈满，追加存储空间
		S->base = (SElemType2*)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(SElemType2));
		if(!S->base) {
			//存储分配失败
			exit(OVERFLOW);
		}
		S->top = S->base + S->stacksize;
		S->stacksize += STACKINCREMENT;
	}
	*S->top++ = e;
	return OK;
}//Push
 
Status Pop2(SqStack2* S, SElemType2* e) {
	//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROE
	if(S->top == S->base) {
		return ERROR;
	}
	*e = *(--S->top);
	return OK;
}//Pop
 
Status DestoryStack2(SqStack2* S) {
	//销毁栈S
	if(S->base) {
		free(S->base);
	}
	S->top = S->base = NULL;
	return OK;
}//DestroyStack
 
Status StackTraverse2(SqStack2 S) {
	//遍历栈，输出每一个数据元素
	SElemType2* p = S.base;
	int i = 0;
	if(S.base == S.top) {
		printf("Stack is Empty.\n");
		return OK;
	}
	while(p < S.top) {
		printf("[%d:%.2lf]", ++i, *p++);
	}
	printf("\n");
	return OK;
}//StackTraverse
 
Status InitList_SqList(SqList* L) {	//构造一个空顺序表L
	L->elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType)); //分配内存
	if(!L->elem)
		exit(OVERFLOW);
	L->length = 0;
	L->listsize = LIST_INIT_SIZE;
	return OK;
}	//InitList_SqList
 
Status ListInsert_SqList(SqList* L, int i, ElemType e) {	//在顺序表L的第i个元素前插入新元素e
	ElemType* newbase, *p, *q;
	if(i == -1) {
		i = L->length + 1;
	}
	if(i < 1 || i > L->length + 1)
		return ERROR;				//插入位置不合法
	if(L->length >= L->listsize) {	//当前存储空间已满，增加分配
		newbase = (ElemType*)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(ElemType));
		if(!newbase)
			return ERROR;			//存储分配失败
		L->elem = newbase;			//新基址
		L->listsize += LISTINCREMENT;	//增加存储容量
	}
	q = &(L->elem[i - 1]);			//q指向插入位置
	for(p = &L->elem[L->length - 1]; p >= q; --p)
		*(p + 1) = *p;				//插入位置之后的数据元素右移
	*q = e;							//插入e
	L->length++;
	return OK;
}	//ListInsert_SqList
 
int ListLength_SqList(SqList L) {	//求顺序表L的长度
	return L.length;
}	//ListLength_SqList;
 
Status Destroy_SqList(SqList* L) {	//销毁一张顺序表
	free(L);
	return OK;
}	//Destroy_SqList
 
void printlist_SqList(SqList L) {	//输出顺序表
	int i;
	for(i = 0; i < L.length; i++)
		printf("%c", L.elem[i]);
	printf("\n");
}	//printlist_SqList;

相关阅读:
使用 python multiprocessing.Queue 出现 too many open files 错误
 java计算机毕业设计ssm智能水务管理系统
 MySQL数据去重
 文心一言 VS 讯飞星火 VS chatgpt （97）-- 算法导论9.3 3题
 【六、http】go的http的客户端重定向
 二、nginx URL重写[rewrite]
从过滤器初识责任链设计模式
 SpringCloud微服务（三）——Zookeeper服务注册中心
 1、Netty适合场景
 ElasticSearch 搜索推荐
原文地址：https://blog.csdn.net/qq_62792553/article/details/127595117