[C++知识库] 栈的应用-计算后缀表达式

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> 栈的应用-计算后缀表达式 -> 正文阅读

[C++知识库]栈的应用-计算后缀表达式

# include <stdio.h>
# include <stdlib.h>
# define M 1024
#define _CRT_SECURE_NO_WARNINGS

typedef int ElemType;
ElemType STACK[M];
int top;
//函数定义
int PUSH(int STACK[], int &top, int item); //注意传递引用类型&
int POP(int STACK[], int &top);
void printStack(int STACK[], int &top);
void INITIALS(int &top);
int Eval(char Express[]); //计算后缀表达式

int main()
{
	 初始化堆栈
	INITIALS(top);
	// 堆栈的应用练习，实现后缀表达式
	char Express[50] = "1563/-2*+#";
	printf("%s\n", Express);
	int result = Eval(Express);
	printf("计算结果;%d\n", result);
	system("pause");
	return 0;
}

// 初始化栈
void INITIALS(int &top)
{
	top = -1;
}

// 压栈
int PUSH(int STACK[], int &top, int item)
{
	if (top == M - 1)
	{printf("stack is full!"); return 0;}
	else
	{
		top = top + 1;
		STACK[top] = item;
		return 1;
	}
}

// 出栈
int POP(int STACK[], int &top)
{
	if (top == -1)
	{ printf("stack is empty!"); return 0; }
	else
	{
		int item = STACK[top];
		top = top - 1;
		return item;
	}
}

// 打印堆栈内容
void printStack(int STACK[], int &top)
{
	for (int i=0; i<=top; i++)
	{
		printf("%d ", STACK[i]);
	}
	//printf("\n");
}

int Eval(char Express[])
{
	int i = 0;
	while (Express[i] != '#')
	{
		if (Express[i] > '0' && Express[i] < '9')
		{
			PUSH(STACK, top, Express[i] - 48); printf("读表达式，压栈%d\n", Express[i] - 48); //ASCII码偏置量
		}
		else if (Express[i] == '+')
		{
			printf("读到加号，当前栈中元素：");
			printStack(STACK, top);
			int T = POP(STACK, top) + POP(STACK, top);
			PUSH(STACK, top, T);
			printf("相加后压栈%d\n", T);
		}
		else if (Express[i] == '-')
		{ 
			printf("读到减号，当前栈中元素：");
			printStack(STACK, top);
			int a = POP(STACK, top);
			int b = POP(STACK, top);
			int T = b - a;
			PUSH(STACK, top, T);
			printf("相减后压栈%d\n", T);
		}
		else if (Express[i] == '*')
		{
			printf("读到乘号，当前栈中元素：");
			printStack(STACK, top);
			int T = POP(STACK, top) * POP(STACK, top);
			PUSH(STACK, top, T);
			printf("相乘后压栈%d\n", T);
		}
		else if (Express[i] == '/')
		{
			printf("读到除号，当前栈中元素：");
			printStack(STACK, top);
			int a = POP(STACK, top); 
			int b = POP(STACK, top);
			int T = b / a;
			PUSH(STACK, top, T);
			printf("相除后压栈%d\n", T);
		}
		i++;
	}
	return POP(STACK, top);
}