栈

Wool Blue 发布于

最后更新于

用数组实现栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 101
int a[MAX_SIZE];  
int top = -1; //定义一个参数top 并指向虚拟索引-1
void Push(int x)  //入栈
{
	if (top == MAX_SIZE - 1)  //判断是否正常
	{
		printf("插入错误!");
		return;
	}
	top++;  
	a[top] = x; 
}
void Pop()  //出栈
{
	if (top == -1)
	{
		printf("删除出错！");
	}
	top--;  
}
int Top()  //获取头元素
{
	return a[top];
}
void Print()  //定义一个输出函数
{
	for (int i = 0; i <= top; i++)
	{
		printf("%d", a[i]);
	}
	printf("\n");
}
int main() 
{
	Push(2);
	Push(3);
	Push(4);
	Print();
	Pop();
	Print();
	Top();
}

链表实现栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <stdio.h>
#include <stdlib.h>

struct Node {    //定义一个节点
	int data;
	struct Node* next;
};
struct Node* top;
void Push(int x)  //入栈 相当于头插法插入链表
{
	//定义插入函数
	
		Node* temp = (Node*)malloc(sizeof(struct Node));//为节点分配空间,注意:必须进行转换，因为malloc返回一个void类型指针
		temp->data = x;   //定义新建节点的值
		temp->next = top;  //top可以看成top->next 这也涵盖链表为空情况
		top = temp;  //将头节点top的指向下一个的指针设为temp的地址   
}
void Pop()  //出栈
{
	struct Node* temp;
	if (top == NULL) return;
	temp = top;  //将top节点指向的值传给temp
	top = temp->next;  //然后将temp指向的节点的next值传给top
	free(temp); //释放temp空间
}
void Print() //迭代打印链表  占用空间多
{
	struct Node* temp = top;
	printf("列表是：");
	while (temp != NULL)  //遍历节点
	{
		printf("%d", temp->data);
		temp = temp->next;
	}
	printf("\n");

}
int main() 
{
	Push(2); 
	Push(3);
	Push(4); 
	Print();
	Pop();
	Print();
}

检查括号的匹配性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<stdio.h>
#include<string.h>
#define MAX 50
char top = -1, stack[MAX];

int full()  //判断栈是否满
{
	if (top == MAX - 1)
		return 1;
	return 0;
}与与与雨雨雨雨雨雨 
int empty()  //判断栈是否空
{
	if (top == -1)
		return 1;
	return 0;
}
void push(char item)  //入栈
{
	if (full())
	{
		printf("栈满了\n");
		return;
	}
	else
	{
		stack[++top] = item;
	}
}
char pop()  //出栈
{
	if (empty())
	{
		printf("栈为空\n");
		return -1;
	}
	return stack[top--];
}
char pair(char c)  //括号判断
{
	if (c == ')')
		return '(';
	else if (c == '}')
		return '{';
	else
	{
		return '[';
	}
}
int main()
{
	char ch, x;
	char exp[50];
	printf("请输入字符串：\n")
	fgets(exp, sizeof(exp), stdin);  //输入括号
	for (int i = 0; i < strlen(exp); i++)
	{
		if (exp[i] == '(' || exp[i] == '{' || exp[i] == '[')
			push(exp[i]);
		else if (exp[i] == ')' || exp[i] == '}' || exp[i] == ']')
		{
			if (empty())
			{
				printf("栈为空，值无效\n");
				return -1;
			}
			else
			{
				x = pair(exp[i]); 
				if (pop()!= x)  //判断后续括号与入栈的是否相同
				{
					printf("前后输入的括号类型不同\n");
					return -1;
				}
			}
		}
		
		
	}
	if (!empty())  //判断读取完后栈是否为空
	{
		printf("括号数量不相等");
	}
}

前缀后缀表达式求值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int IsNumber(char c); //判断字符是不是数字
int IsOperator(char c);  //判断字符是不是操作符
int Perform(char operation, int operand1, int operand2); //执行操作并返回结果
int CalculatePostfix(char* expression);  //计算后缀
int main()
{
	char expression[100];
	printf("请输入后缀表达式：");
	fgets(expression, sizeof(expression), stdin);
	expression[strcspn(expression, "\n")] = '\0'; // 去除换行符


	int result = CalculatePostfix(expression);
	printf("输出结果为：%d\n", result);

	return 0;
}



int IsNumber(char c) //判断字符是不是数字
{
	if (c >= '0' && c <= '9')
		return 1;
	return 0;
}
int IsOperator(char c)  //判断字符是不是操作符
{
	if (c == '+' || c == '-' || c == '*' || c == '/')
		return 1;
	return 0;
}
int Perform(char operation, int operand1, int operand2) //执行操作并返回结果
{
	if (operation == '+')
		return operand1 + operand2;
	else if (operation == '-')
		return operand1 - operand2;
	else if (operation == '*')
		return operand1 * operand2;
	else if (operation == '/')
		return operand1 / operand2;

	printf("出现错误\n");
	return -1;
}
int CalculatePostfix(char* expression)  //计算后缀
{
	int* stack = (int*)malloc(strlen(expression) * sizeof(int));//动态内存分配创建栈
	int top = -1;

	for (int i = 0; i < strlen(expression); i++) 
	{
		//从左向右扫描字符，如果是分隔符，则继续
		if (expression[i] == ' ' || expression[i] == ',')
			continue;

		//如果字符是操作符，则从栈中弹出两个操作数并进行操作，将结果压入栈中
		else if (IsOperator(expression[i]))
		{
			//弹出两个操作数
			int operand2 = stack[top--];
			int operand1 = stack[top--];
			//执行运算操作
			int result = Perform(expression[i], operand1, operand2);
			//将结果压入栈中
			stack[++top] = result;
		}
		else if (IsNumber(expression[i]))
		{   //字符中提取数字操作符
			//只要提取到数字字符，就将其转化为整数，并压入栈中
			int operand = 0;
			while (i < strlen(expression) && IsNumber(expression[i]))
			{  //对于多位数，每次获取到右侧的数字字符时，将当前操作符乘以10并再加上新的数字
				operand = (operand * 10) + (expression[i] - '0');
				i++;
			}
			i--;
			//将操作符压入栈中
			stack[++top] = operand;
		}
	}
	//如果表达式格式正确，栈最终只会剩下一个元素，即计算结果
	int result = stack[top];
	free(stack);  //释放内存
	return result;
}

中缀表达式转换为后缀表达式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/*
算法描述：将中缀表达式中的数字拿出，然后从左向右将符号压入栈中，如果当前符号比栈中的符号的优先级高
则压入栈中，如果当前符号比栈中的符号优先级低，则释放栈中符号
当表达式中有括号时，先将左括号压入栈中，直到扫描到右括号，释放括号。
*/
// 将中缀表达式转换为后缀表达式的函数
char* InfixToPostfix(char* expression);

// 判断运算符的优先级
int HasHigherPrecedence(char operator1, char operator2);

// 判断字符是否为运算符
int IsOperator(char C);

// 判断字符是否为字母或数字
int IsOperand(char C);

int main()
{
	char expression[100];
	printf("请输入中缀表达式：\n");
	fgets(expression, sizeof(expression), stdin);
	char* postfix = InfixToPostfix(expression);
	printf("后缀表达式为：%s\n", postfix);
	free(postfix);
	return 0;
}

// 将中缀表达式转换为后缀表达式
char* InfixToPostfix(char* expression)
{
	char* postfix = (char*)malloc(strlen(expression) * sizeof(char)); // 存储后缀表达式的字符串
	int postfixIndex = 0; // 后缀表达式字符串的索引
	int i = 0; // 中缀表达式字符串的索引

	while (expression[i] != '\0') {
		if (expression[i] == ' ' || expression[i] == ',') {
			i++;
			continue;
		}
		else if (IsOperator(expression[i])) { // 如果是运算符
			while (postfixIndex > 0 && postfix[postfixIndex - 1] != '(' && HasHigherPrecedence(postfix[postfixIndex - 1], expression[i])) {
				postfix[postfixIndex++] = postfix[postfixIndex - 1]; // 将栈顶的运算符加入到后缀表达式中
				postfixIndex--;
			}
			postfix[postfixIndex++] = expression[i]; // 将当前运算符加入到后缀表达式中
		}
		else if (IsOperand(expression[i])) { // 如果是字母或数字
			postfix[postfixIndex++] = expression[i]; // 将字母或数字加入到后缀表达式中
		}
		else if (expression[i] == '(') { // 如果是左括号
			postfix[postfixIndex++] = expression[i]; // 将左括号加入到后缀表达式中
		}
		else if (expression[i] == ')') { // 如果是右括号
			while (postfixIndex > 0 && postfix[postfixIndex - 1] != '(') {
				postfix[postfixIndex++] = postfix[postfixIndex - 1]; // 将栈顶的运算符加入到后缀表达式中
				postfixIndex--;
			}
			postfixIndex--; // 将左括号从后缀表达式中移除
		}
		i++;
	}

	while (postfixIndex > 0) {
		postfix[postfixIndex++] = postfix[postfixIndex - 1]; // 将栈中剩余的运算符加入到后缀表达式中
		postfixIndex--;
	}

	return postfix;
}

// 判断字符是否为字母或数字
int IsOperand(char C)
{
	if (C >= '0' && C <= '9') return 1;
	if (C >= 'a' && C <= 'z') return 1;
	if (C >= 'A' && C <= 'Z') return 1;
	return 0;
}

// 判断字符是否为运算符
int IsOperator(char C)
{
	if (C == '+' || C == '-' || C == '*' || C == '/' || C == '$')
		return 1;
	return 0;
}

// 判断运算符的优先级
int HasHigherPrecedence(char op1, char op2)
{
	int op1Weight = 0;
	int op2Weight = 0;

	switch (op1)
	{
	case '+':
	case '-':
		op1Weight = 1;
		break;
	case '*':
	case '/':
		op1Weight = 2;
		break;
	case '$':
		op1Weight = 3;
		break;
	}

	switch (op2)
	{
	case '+':
	case '-':
		op2Weight = 1;
		break;
	case '*':
	case '/':
		op2Weight = 2;
		break;
	case '$':
		op2Weight = 3;
		break;
	}

	if (op1Weight == op2Weight) {
		return 1; // 如果运算符的优先级相同，则返回1
	}
	else {
		return op1Weight > op2Weight ? 1 : 0; // 如果op1的优先级高于op2，则返回1，否则返回0
	}
}
Wool Blue

Wool Blue

学习新思想，争做好青年

21
2
6
TOC
  1. 1. 用数组实现栈
  2. 2. 链表实现栈
  3. 3. 检查括号的匹配性
  4. 4. 前缀后缀表达式求值
  5. 5. 中缀表达式转换为后缀表达式
CATEGORYS
TAGS
Hadoop Python 前端 数据库 数据结构 机器学习