当前位置：首页 > news >正文

数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值特殊矩阵的压缩存储

news 2025/9/13 10:46:16

文章目录

栈的应用
- 1.栈的括号匹配
- 代码实战:
- 问题分析:
- 2.栈的表达式求值
- - 2.1 中缀、后缀、前缀表达式
  - 2.2 中缀表达式改写为后缀表达式(手算)
  - 2.3 后缀表达式的计算(手算)
  - 2.4 中缀表达式转前缀表达式（手算)和计算前缀表达式
  - 2.5后缀表达式的计算(机算)
  - 2.6 中缀表达式转后缀表达式（机算)
  - 2.7 中缀表达式的计算（栈实现)
3.矩阵的压缩存储
- 3.1 对称矩阵的压缩存储
- 3.2 三角矩阵的压缩存储
- 3.3 三对角矩阵(带状矩阵)
- 3.4 稀疏矩阵压缩存储
- - 3.4.1 存储方法一结构体方式存储
  - 3.4.2 存储方法二十字链表法

栈的应用

1.栈的括号匹配

问题分析:
问题还是很简单就是,利用栈的特性,左括号进栈,右括号出栈实现匹配,在栈空且所有括号都扫过一遍后结束
在这里插入图片描述

代码实战:

南京理工大学上机题目

苗苗今天刚刚学会使用括号，不过他分不清小括号，中括号，大括号和尖括号，不知道怎么使用这些括号，请帮助他判断括号使用是否正确。

注意：不需要区分括号的优先级。

输入格式
共一行，包含一个由 <,(,{,[,>,),},] 构成的字符串。

输出格式
如果输入的字符串中的括号正确匹配则输出 yes，否则输出 no。

数据范围
输入字符串长度不超过 10000

输入样例：

(){}

输出样例：

yes

问题分析:

想到用栈来实现括号匹配的问题
第一步,肯定是实现栈的基础操作(当然为了简单快捷,选择静态存储的方式实现栈)
- 栈的定义
- 栈的初始化
- 入栈
- 出栈
- 判空
具体问题具体分析
- 写一个括号匹配函数,模拟整个过程
- 主函数中补上字符串的输入

完整代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MaxSize 100001
typedef struct{char data[MaxSize]; //静态数组存放栈中元素 int top;           // 栈顶元素 
}SqStack;void InitSqStack(SqStack &S)
{S.top=-1;
}bool StackEmpty(SqStack S)
{if(S.top==-1)return true;return false;
}bool Push(SqStack &S,char x)
{S.data[++S.top]=x;return true;
}bool Pop(SqStack &S,char &x)
{x=S.data[S.top--];return true;
}bool BracketCheck(char str[])
{SqStack S;InitSqStack(S);for(int i=0;i<strlen(str);i++)    //-1是因为fgets函数读入最后一个字符是/n要去掉 {if(str[i]=='<'||str[i]=='('||str[i]=='{'||str[i]=='[') //匹配到左括号 {Push(S,str[i]);}else                                                   //匹配到右括号 {	char x; Pop(S,x);if(str[i]=='>'&&x!='<')return false;if(str[i]==')'&&x!='(')return false;if(str[i]=='}'&&x!='{')return false;if(str[i]==']'&&x!='[')return false;}}return StackEmpty(S); //检索完全部括号后，栈空说明匹配成功
}
int main()
{char str[MaxSize];fgets(str,MaxSize,stdin);// 检查字符串的最后一个字符是否为换行符，并去除它  int len = strlen(str);  if (len >0&&str[len-1] =='\n') {  str[len-1] ='\0';  }  if(BracketCheck(str))printf("yes");else printf("no");
}