C语言编程练习day17

1、栈的应用_后缀表达式求解
通过之前链栈的相关API来辅助完成。需要在新项目中导入linkStack.h和linkStack.c两个文件(在C语言编程练习day13中有).
思路：遍历后缀表达式。1、遇到数字，直接进栈。2、遇到符号，从栈中弹出两个数，第一个数作为右操作数，第二个作为左操作数，然后根据符号进行运算并将运算的结果压入栈。遍历结束后，栈中剩下的唯一数字，就是计算结果。
输入：831-5 *+
输出：18
优化目标：无
完整代码：

#include 
#include 
#include 

#include "linkStack.h"

//数据结构体
typedef struct MYDATA {
	linkNode node;
	int val;
}MyData;


int isNumber(char c) {
	return c >= '0' && c <= '9';
}


int Calculate(int leftNum, int rightNum, char c) {
	int result = 0;
	switch (c)
	{
	case '+':
		result = leftNum + rightNum;
		break;
	case '-':
		result = leftNum - rightNum;
		break;
	case '*':
		result = leftNum * rightNum;
		break;
	case '/':
		result = leftNum / rightNum;
		break;
	default:
		break;
	}
	return result;
}


int main() {
	//后缀表达式
	char* str = "831-5*+";
	char* p = str;

	//初始化栈
	linkStack* stack = Init_linkStack();

	while (*p != '') {
		if (isNumber(*p)) {
			//如果扫描到操作数，直接进栈
			MyData* data = (MyData*)malloc(sizeof(MyData));
			data->val = *p - '0';
			//入栈
			Push_linkStack(stack, (linkNode*)data);
		}else {//扫描到操作符
			//从栈中弹出第一个数，作为右操作数
			MyData* right = (MyData*)Top_linkStack(stack);
			int rightNum = right->val;
			Pop_linkStack(stack);
			free(right);

			//从栈中弹出第一个数，作为左操作数
			MyData* left = (MyData*)Top_linkStack(stack);
			int leftNum = left->val;
			Pop_linkStack(stack);
			free(left);

			//计算结果，并压入栈
			int ret = Calculate(leftNum, rightNum, *p);
			MyData* result = (MyData*)malloc(sizeof(MyData));
			result->val = ret;
			Push_linkStack(stack, (linkNode*)result);
		}

		p++;
	}

	//打印栈中的最后一个数
	if (Size_linkStack(stack) == 1) {
		MyData* num = (MyData*)Top_linkStack(stack);
		printf("%d", num->val);
		Pop_linkStack(stack);
		free(num);
	}
	//释放栈
	FreeSpace_linkStack(stack);

	return 0;
}

2、栈的应用_括号匹配
思路：扫描字符串，如果是左括号，则直接入栈。如果是右括号，如果栈不空，从栈顶弹出一个括号，匹配成功；如果栈空，则该右括号没有可匹配的左括号，则指出其位置。当扫描完字符串时，若栈不空，则栈中剩余括号都没有可匹配的右括号。
输入：(1-2))+(((6+)*3+((8+8)
输出：

优化目标：无

完整代码

#include 
#include 
#include 

#include "linkStack.h"

typedef struct MYCHAR {
	linkNode node;
	char* pAddress;
	int index;
}MyChar;


int isLeft(char c) {
	return c == '(';
}


int isRight(char c) {
	return c == ')';
}


void Print(int pos, char* str) {
	printf("%sn", str);
	for (int i = 0; i < pos; i++) {
		printf(" ");
	}
	printf("%c", 'A');
	printf("n");
}

int main() {
	
	char* str = "(1-2))+(((6+)*3+((8+8)";
	char* p = str;
	int index = 0;

	//初始化栈
	linkStack* stack = Init_linkStack();

	while (*p != '') {
		if (isLeft(*p)) {
			//如果是左括号，直接进栈
			MyChar* mychar = (MyChar*)malloc(sizeof(MyChar));
			mychar->pAddress = p;
			Push_linkStack(stack, (linkNode*)mychar);
			mychar->index = index;
		}
		//右括号
		if (isRight(*p)) {
			//如果栈不空，则出栈
			if (Size_linkStack(stack) > 0) {
				Pop_linkStack(stack);
			}else {
				//该右括号没有匹配的左括号，打印输出其位置
				printf("没有匹配的右括号n");
				
				Print(index, str);
			}
		}

		index++;
		p++;
	}

	//如果栈不空,则有没有匹配的左括号
	while (Size_linkStack(stack) > 0) {
		printf("没有匹配的左括号n");
		MyChar* mychar = (MyChar*)Top_linkStack(stack);
		Print(mychar->index, str);
		Pop_linkStack(stack);
		free(mychar);
	}

	//释放栈
	FreeSpace_linkStack(stack);
	return 0;
}

总结：今天写了栈应用中的括号匹配和后缀表达式求值。明天学写查找相关知识。