【栈经典问题剖析】上
1.1进制转换
1.1.2思路图解：
- 每次将得到的余数存入栈中，直到商为0时，停止入栈。
- 依次将栈中元素出栈并进行打印操作（注意负数的符号情况）
//进制转换：10进制整数转换成8进制整数
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100 // 定义栈的最大大小
//定义栈结构
typedef struct
{
int data[MAXSIZE];
int top;
} Stack;
// 初始化栈
void initStack(Stack* s)
{
s->top = -1;
}
// 判断栈是否为空
int StackEmpty(Stack* s)
{
return s->top == -1;
//为空返回非零值，不为空返回0
}
// 判断栈是否已满
int StackFull(Stack* s)
{
return s->top == MAXSIZE - 1;
//为空返回非零值，不为空返回0
}
// 入栈操作
void push(Stack* s, int value)
{
if (StackFull(s))
{
printf("栈满！\n");
return;
}
s->data[++(s->top)] = value;
//先自增，再入栈
}
// 出栈操作
int pop(Stack* s)
{
if (StackEmpty(s))
{
printf("栈空!\n");
exit(1);//异常终止
}
return s->data[(s->top)--];
//先出栈再自减
}
// 十进制数转换为八进制数（核心）
//传入一个十进制数
void decimalToOctal(int decimal1)
{
//[1]建立并初始化一个栈
Stack stack;
initStack(&stack);
//[2]处理零的情况
if (decimal1 == 0)
{
printf("0");
return;
}
//[3]取绝对值，因为十进制数可能为负数
int decimal = abs(decimal1);
//[3]将十进制数转换为八进制数并将余数压入栈中
while (decimal != 0)
{
int remainder = decimal % 8;//计算余数
push(&stack, remainder);//将每次余数入栈
decimal /= 8;//更改被除数
}
//[4]从栈顶依次弹出余数并打印，组成八进制数
//<1>若数字为负数，则打印负号
if (decimal1 < 0)
{
printf("-");
}
//<2>正常出栈并打印
while (!StackEmpty(&stack))
{
printf("%d", pop(&stack));
}
}
int main()
{
int decimal;
printf("请输入一个10进制整数: ");
scanf_s("%d", &decimal);
printf("转换成的八进制整数为: ");
decimalToOctal(decimal);
return 0;
}
1.2括号匹配问题
括号不匹配的情况分析：
1.2.1算法思路：
- (1)定义一个栈，用来存储左括号
- (2)定义一个标记符号flag，用来表示括号是否匹配
- (3)从头到尾遍历字符串，
- <1>若当前字符为左括号则入栈
- <2>若当前字符为右括号则进行匹配：
- [1]当前字符与栈顶字符相同，匹配成功，继续向下循环
- [2]当前字符与栈顶字符不同，匹配失败；更改flag=0
- <3>判断当前flag的状态，若为0，证明括号字符串非法，退出循环
- <4>非法的两种情况：
- [1]flag==0:匹配失败
- [2]遍历完后，栈为空：有多余的左括号
//括号匹配问题
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define MAXSIZE 100 // 定义栈的最大大小
//定义栈结构
typedef struct
{
char data[MAXSIZE];
int top;
} Stack;
// 初始化栈
void initStack(Stack* s)
{
s->top = -1;
}
// 判断栈是否为空
int StackEmpty(Stack* s)
{
return s->top == -1;
//为空返回非零值，不为空返回0
}
// 判断栈是否已满
int StackFull(Stack* s)
{
return s->top == MAXSIZE - 1;
//为空返回非零值，不为空返回0
}
// 入栈操作
void push(Stack* s, char value)
{
if (StackFull(s))
{
printf("栈满！\n");
return;
}
s->data[++(s->top)] = value;
//先自增，再入栈
}
// 出栈操作
char pop(Stack* s)
{
if (StackEmpty(s))
{
printf("栈空!\n");
exit(1);//异常终止
}
return s->data[(s->top)--];
//先出栈再自减
}
//判断是否非法：(核心)
bool solve(char * str)
{
Stack s;
Stack* s1 = &s;
initStack(s1);
int flag = 1;//默认合法
for (int i=0;i<strlen(str);i++)
{
//[1]若当前字符为左括号则入栈
if(str[i]=='('||str[i]=='['||str[i]=='{')
{
push(s1, str[i]);
}
//[2]若当前字符为右括号则进行匹配：
else
{
switch (str[i])
{
case')':
if (!StackEmpty(s1) && s1->data[s1->top] == '(')
{
pop(s1);
}
else
{
flag = 0;
}
break;
case']':
if (!StackEmpty(s1) && s1->data[s1->top] == '[')
{
pop(s1);
}
else
{
flag = 0;
}
break;
case'}':
if (!StackEmpty(s1) && s1->data[s1->top] == '{')
{
pop(s1);
}
else
{
flag = 0;
}
break;
}
}
//[3]判断当前flag的状态，若为0，证明括号字符串非法，退出循环
if (flag == 0)
{
break;
}
}
//[4]非法字符串的判断
if (flag==0||!StackEmpty(s1))
{
return false;
}
else
{
return true;
}
}
int main()
{
char str[100];
scanf_s("%s", str, (unsigned)sizeof(str));
if (solve(str)==true)
{
printf("合法！:%s\n",str);
}
else
{
printf("非法！:%s\n",str);
}
}
