[数据结构与算法]链栈的后缀表达式求值-----数据结构与算法笔记

一、链栈表示

参考书：《数据结构（C语言）》–严蔚敏等编著，清华大学出版社。

1、链栈的后缀表达式求值操作

链栈的表示比较与顺序栈相对更简单，并且存在如下优点：

链栈的头指针就是栈顶；
不需要头结点；
基本不存在栈满情况；
插入删除在栈顶实现；

链栈表示如图：

相关代码：

#include "stdio.h"
#include "stdlib.h"
#define TRUE     1
#define FALSE    0
#define OK       1
#define ERROR    0
#define OVERFLOW -2

typedef int Status;
typedef int SElemType;
typedef struct StackNode {
	SElemType data;			//栈元素
	struct StackNode *next;	//链栈指针，作为栈的栈顶
} StackNode, *LinkStack;

Status InitStack_S(LinkStack &S);
//构造一个链栈L
Status InitStack_S(LinkStack &S) {
	S=NULL;	//空链栈 
	return OK;
}

Status Push_S(LinkStack &S,SElemType e);
//链栈入栈
Status Push_S(LinkStack &S,SElemType e) {
	LinkStack p;
	p = new StackNode;
	p->data = e;
	p->next = S;
	S = p;		//更新头指针的指向
	return OK;
}

Status Pop_S(LinkStack &S,SElemType &e);
//链栈出栈，用e返回
Status Pop_S(LinkStack &S,SElemType &e) {
	LinkStack p;
	if(S == NULL) return ERROR;
	p = new StackNode;
	e = S->data;	//将顶元素data值给e 
	p = S;	//p指向S(顶) 
	S = S->next;	//S向下移 
	free(p);	//释放顶节点 
	return OK;
}

Status Operator_S(int e1,char ch,int e2);
//操作
Status Operator_S(int e1,char ch,int e2) {
	switch(ch) {
		case '+': return e1+e2; break;
		case '-': return e1-e2; break;
		case '*': return e1*e2; break;
		case '/': return e1/e2; break;
	}
}

int main(void) {
	LinkStack S;
	InitStack_S(S);
	char ch;
	int c,e1,e2,result;
	scanf("%c",&ch);
	while(ch!='#') {
		if(ch == '+' || ch=='-' || ch=='*' || ch=='/') {
			Pop_S(S,e2);
			Pop_S(S,e1);
			result = Operator_S(e1,ch,e2);
			Push_S(S,result);
		} else {
			c=ch-'0';	//遇到数值 进栈 
			Push_S(S,c);
		}
		scanf("%c",&ch);
	}
	Pop_S(S,result);
	printf("%d",result);
	return 0;
}

/*
输入：931–3*+82/+#（#代表输入结束）
输出：19
输入：2278---#（注意这里是三个-号）
输出：-1
*/