栈的链式储存结构及应用：四则运算表达式求值（中缀表达式转化为后缀表达式并求值）

遇到的问题一：Segmentation Fault（存储器区块错误）
遇到的问题二：函数内变量一经声明其地址已固定，导致同一结点反复入栈
遇到的问题三：对字符串如何标记和提取单个数值

/*/////////////////////////////////////
通过链栈将中缀表达式转换为后缀表达式并计算出结果
2022·10·14：完成转换部分
2022·10·15/16：完成运算部分
待实现：
支持小数运算
*//////////////////////////////////////

#include<stdio.h>
#include<string>
#include<stdlib.h>
#include<math.h>

#define MAX_LENGTH 100
#define NUM 1
#define OPERATOR 0
#define DELIMITER '#'
//判断字符a是否为数字（注：宏定义判断表达式时，建议带上括号，以免取反时出错）
#define ISNUM(a) (a >= '0' && a <= '9')
//判断运算符a的优先级是否不低于或等于（遗漏！）运算符b
#define ISPRIORITY(a, b) (((a == '*' || a == '/') && (b == '-' || b == '+')) || ((a == '+' || a == '-') && b == '('))
#define CHAR_TO_NUM(a) (a - '0')

typedef bool Type; 
typedef int Info;
//链表结点的信息
typedef struct StackNode 
{
	Info info;//字符信息
	StackNode *next;//指向下一个结点
}StackNode, *StackPtr;
//头结点，保存链栈的整体信息
typedef struct LinkStack
{
	Type type;//结点变量info的类型（char/int）
	int count;
	StackPtr top;//指向首结点
}LinkStack;

StackNode* Pop(LinkStack *link);
void Push(int info, LinkStack *link);
void Inquire_Print(Type type, Info info);
char *Translate(LinkStack *link, char *_formula);
int Calculate(LinkStack *link, char *formula_);

//出栈操作
StackNode* Pop(LinkStack *link)
{

	StackNode* pop = link->top;

	//更新头节点的信息
	link->top = ((link->top)->next);
	link->count --;
	//出栈的结点指向的下一个结点为空
	pop->next = NULL;

	Inquire_Print(link->type, pop->info);
	printf("已出栈\n");
	
	return pop;
}

void Push(int info, LinkStack *link)
{
	
	/*
	2022·10·13 
	函数内定义的变量地址固定，因此需要为入栈结点动态分配内存
	否则每次入栈的结点实际上为同一个结点（因为地址相同）
	方法一： 通过malloc()动态分配内存
	方法二： 通过free()释放被分配的内存
	*/
	//开辟一处空间储存新入栈的结点
	/*
		函数malloc
		包含于stdlib.h 
		返回一个void类型的地址，建议强制类型转换为所需类型
	*/
	/*
		函数malloc
		包含于stdlib.h 
		返回一个void类型的地址，建议强制类型转换为所需类型
	*/
	StackPtr push = (StackPtr)malloc(sizeof(StackNode));
		
	push->info = info;
	push->next = link->top;
	
	link->top = push;
	link->count ++;
	
	Inquire_Print(link->type, push->info);
	printf("已入栈\n");
} 

void TraverseNode(LinkStack *link)
{
	StackPtr nodePtr = link->top;
	
	printf("当前栈内情况：\n");
	
	while(nodePtr != NULL)
	{
		if(link->type == NUM)
		{
			printf("%3d\n", nodePtr->info);
		}
		if(link->type == OPERATOR)
		{
			printf("%3c\n", nodePtr->info);
		}
		nodePtr = nodePtr->next;
	}
}

void Inquire_Print(Type type, Info info)
{
	switch(type)
	{
	case NUM:printf("数字%d", info);break;
	case OPERATOR:printf("字符%c", info);break;
	}
}

char* Translate(LinkStack *link, char *_formula)
{
	//当前栈内的信息类型为运算符
	link->type = OPERATOR;
	char *formula_ = (char *) malloc(sizeof(char[MAX_LENGTH]));
	/*
		遍历各个字符，将中缀表达式转换为后缀表达式
	*/ 
	//i，j分别为遍历两个表达式的下标，i随循环自增，j随元素放入自增
	for(int i = 0, j = 0; _formula[i] != '\0'; i ++)
	{
		printf("遍历到%c\n", _formula[i]);
		//如果字符为数字，则放入后缀表达式中
		if(ISNUM(_formula[i]))
		{
			printf("放入后缀表达式中\n");
			formula_[j ++] = _formula[i];	
			if(!ISNUM(_formula[i + 1]))
			{
				printf("单个值遍历完毕，添加分隔符！\n");
				formula_[j ++] = DELIMITER;
			}		
		}
		else if (_formula[i] == '(')
		{
			Push(_formula[i], link);
		}
		else if(_formula[i] == ')')
		{
			if(link->top != NULL)
			{
				while(link->top->info != '(')
				{
					formula_[j ++] = Pop(link)->info;
					//找不到左空格
					if(link->top != NULL)
					{
						pritnf("错误：无法匹配左括号’(‘,即将越界访问内存！\n");
					}
				}
				Pop(link);
			}
			else
			{
				printf("Error!\n");
				return NULL;
			}
		}
		else
		{
		/*
			如果待入栈运算符的优先级不高于（如果包含等于会导致结合方向出错）栈顶运算符，则入栈
			否则弹出栈顶运算符，直至条件成立再入栈
		*/ 	
			//防止指针越界访问内存导致程序错误 
			if(link->top != NULL)
			{	
				while(!ISPRIORITY(_formula[i], link->top->info))
				{
					printf("待入栈运算符优先级较低，栈顶运算符出栈！\n");
					formula_[j ++] = Pop(link)->info;
					TraverseNode(link);
					//防止指针越界访问内存导致程序错误 
					if(link->top == NULL)
						break;
				}
			}	
			Push(_formula[i], link);
			TraverseNode(link);
		}
		/*
		如果前缀表达式已经遍历完毕，
		则将栈内运算符弹出放入后缀表达式，补上结束符'\0' 
		*/
		if(_formula[i + 1] == '\0')
		{
			printf("遍历完成，全部出栈！\n");
			while(link->top != NULL)
			{
				formula_[j ++] = Pop(link)->info;
				TraverseNode(link);
				
			}
			formula_[j] = '\0';		
		}
	}	
	return formula_;
}

int Calculate(LinkStack *link, char *formula_)
{
	int result = 999999;
	int numTmp = 0;

	printf("开始运算：\n");
	link->type = NUM;
	for(int i = 0; formula_[i] != '\0'; i ++)
	{
		if(ISNUM(formula_[i]))
		{
			numTmp += CHAR_TO_NUM(formula_[i]);
			printf("数字%d放入待入栈值的个位\n", numTmp);
			if(formula_[i + 1] != DELIMITER)
			{
				numTmp *= 10;
				printf("后方有连续数字，待入栈值提高一位\n", numTmp);
			}
			else
			{
				Push(numTmp, link);
				numTmp = 0;
				printf("单个值已获取，入栈\n", numTmp);
			}
		}
		else if(formula_[i] == '+')
		{
			int sum = Pop(link)->info + Pop(link)->info;
			printf("加法运算，和%d入栈\n", sum);
			Push(sum, link);
		}
		else if(formula_[i] == '-')
		{
			int b = Pop(link)->info;
			int a = Pop(link)->info;
			Push(a - b, link);
			printf("减法运算，差%d入栈\n", a - b);
		}
		else if(formula_[i] == '*')
		{
			int mulitiply = Pop(link)->info * Pop(link)->info;
			Push(mulitiply, link);
			printf("乘法运算，积%d入栈\n", mulitiply); 
		}
		else if(formula_[i] == '/')
		{
			int b = Pop(link)->info;
			int a = Pop(link)->info;
			Push(a / b, link);
			printf("除法运算， 商%d入栈\n", a / b);
		}
	}

	return result = Pop(link)->info;
}

int main()
{
	char _formula[MAX_LENGTH]; //中缀表达式
	char *formula_; //后缀表达式
	int result = 99999;

	formula_ = (char *) malloc(sizeof(char[MAX_LENGTH]));
	LinkStack linkStack; //头节点
	linkStack.top = NULL; //头节点
	linkStack.count = 0;
	
	printf("输入一个中缀表达式：\n"); 
	//gets函数在C/C++11后被弃用，C/C++14后被移除
	gets(_formula);
	formula_ = Translate(&linkStack, _formula);
	printf("转化为后缀表达式："); 
	puts(formula_);
	result = Calculate(&linkStack, formula_);
	printf("运算结果为：%d", result);
	getchar();
	
	 
	return 0;
}