顺序栈

顺序栈

此字符匹配算法，是用栈思想实现的。故而可以放在栈的章节中讲解。

*** 作系统 - Windows10
编译环境 - Visual Studio 2022 Preview

算法步骤

来看看书上对这个算法的步骤描述吧。

1、	初始化OPTR栈和OPND栈，
	将表达式起始符号"#"压入OPTR栈。  
2、	扫描表达式，读入第一个字符ch，
	如果表达式没有扫描完毕至“#”或OPTR的栈顶元素不为"#"时，
	则循环执行以下 *** 作:  
	（1）若ch不是运算符，
		则压入OPND栈，读入下一字符ch; 
	（2）若ch是运算符，
		则根据OPTR的栈顶元素和ch的优先级比较结果，
		做不同的处理:
		1）若是小于，
			则ch压入OPTR栈，读入下一字符ch; 
		2）若是大于，
			则d出OPTR栈顶的运算符，
			从OPND栈d出两个数，进行相应运算，
			结果压入OPND栈;
		3）若是等于，
			则OPTR的栈顶元素是“(”且 ch是“)”,
			这时d出OPTR栈顶的“(”，
			相当于括号匹配成功，然后读入下一字符ch。
3、OPND栈顶元素即为表达式求值结果，返回此元素。

汝听，人言否？

OPTR定义的是一个栈，用来保存+、-、* 、/ 四个运算符。

OPND栈用来保存数值。这里只能保存1位的数。

运行结果

输入 1+2*3-4/4#（#是终止符）

得到计算步骤以及最终的运算结果

源码

#include 
#define MAXSIZE 100
typedef struct Stack
{
	int *top;// int* top - 声明top为一个int型指针
	int *base;
	int size;
}St;

void Init(St& S)
{
	S.base = new int[MAXSIZE];
	if (!S.base)
		exit(OVERFLOW);
	S.top = S.base;
	S.size = MAXSIZE;
	printf("初始化成功n");
}

bool CharPush(St& S,char c)
{
	if (S.top - S.base == MAXSIZE)
		return false;
	*S.top = c;//*s.top - top是s变量的成员指针，用*访问top指向的内容
	S.top++;// s.top - s是变量，访问属于它的成员变量top
	printf("[CharPush]%c入栈成功n", c);
	return true;
}

char CharPop(St& S)
{
	if (S.top == S.base)
		return false;
	S.top--;
	printf("[CharPop]%c出栈成功n", *S.top);
	return *S.top;
}

bool IntPush(St& S, int n)
{
	if (S.top - S.base == MAXSIZE)
		return false;
	*S.top = n;//*s.top - top是s变量的成员指针，用*访问top指向的内容
	S.top++;// s.top - s是变量，访问属于它的成员变量top
	printf("[IntPush]%d入栈成功n", n);
	return true;
}

int IntPop(St& S)
{
	if (S.top == S.base)
		return false;
	S.top--;
	printf("[IntPush]%d出栈成功n", *S.top);
	return *S.top;
}

char GetTop(St& S)
{
	if (S.top == S.base)
		return NULL;
	return *(S.top - 1);
}

bool In(char c)// 判断是否为运算符的函数
{
	if (c >= '#' && c <= '/')
		return true;
	return false;
}

char Precede(char c1, char c2)
{
	switch (c1)
	{
	case '+':// 我们俩的优先级相同，可以放在一起
	case '-':
		switch (c2)
		{
		case'+':
		case'-':
		case')':
		case'#':
			return '>';
			break;
		case'*':
		case'/':
		case'(':
			return '<';
			break;
		}
	case'*':// 除了左括号，我们无所畏惧
	case '/':// 我同意楼上所言
		if (c2 == '(')
		{
			return '<';
			break;
		}
		else 
		{
			return '>';
			break;
		}
	case'(':// 没有人比我左括号更小，但是我不能和#比
		if (c2 == '(')
		{
			printf("Error:左括号遇到了#号 程序结束n");
			break;
		}
		else if (c2 == ')')
		{
			return '=';
			break;
		}
		return '<';
		break;
	case')':// 我是站在关系链顶端的右括号，没有人比我大，但是我不能和左括号比
		if (c2 == '(')
		{
			printf("Error:右括号遇到了左括号n");
			break;
		}
		return '>';
		break;
	case'#':// 我和左括号一样，处于优先关系链底端，我不和右括号比
		if (c2 == '#')
		{
			return '=';
			break;
		}
		else if (c2 == ')')
		{
			printf("#号遇到了右括号n");
			break;
		}
		return '<';
		break;
	}
}

int Operate(int a, char theta, int b)
{
	printf("[Operate]t");
	switch (theta)
	{
	case '+':
		std::cout << a << "+" << b << "=" << a + b << "n";
		return a + b;
		break;
	case '-':
		std::cout << a << "-" << b << "=" << a - b << "n";
		return a - b;
		break;
	case '*':
		std::cout << a << "*" << b << "=" << a * b << "n";
		return a * b;
		break;
	case '/':
		std::cout << a << "/" << b << "=" << a / b << "n";
		return a / b;
		break;
	default:
		printf("运算符有问题n");
		break;
	}
	return 0;
}

int main()
{
	char ch = ' ';
	char theta = ' ';
	St OPND;// 数字栈
	St OPTR;// 字符栈
	int a, b;

	Init(OPND);// 数字栈
	Init(OPTR);// 字符栈
	CharPush(OPTR, '#');
	std::cin >> ch;
	while (ch != '#' || GetTop(OPTR) != '#')
	{
		if (!In(ch))// 如果不是运算符 说明是数字
		{
			ch -= 48;
			IntPush(OPND, ch);// 数字栈入栈
			std::cin >> ch;
		}
		else// 这个else可以去掉吗 
		{
			switch (Precede(GetTop(OPTR), ch))
			{
			case '<':
				CharPush(OPTR, ch);
				std::cin >> ch;
				break;
			case '>':
				theta = CharPop(OPTR);
				b = IntPop(OPND);
				a = IntPop(OPND);
				IntPush(OPND, Operate(a, theta, b));
				break;
			case '=':
				char x = CharPop(OPTR);
				std::cin >> ch;
				break;
			}
		}
	}
	int q = IntPop(OPND);
	std::cout << q;
	return 0;
}