09黑马笔记之栈的应用_中缀表达式转后缀表达式
1 前提：
1）数字：直接输出。
2）左括号：直接进栈(优先级默认最低)。
3）右括号：将栈顶符号输出，直到匹配到左括号。
4）运算符：1)若一开始没有可比较直接进栈; 2)若栈顶元素优先级低，进栈; 3)若栈顶元素优先级高，将栈顶元素弹出并输出，直至低就进栈。
//最后将栈中的元素遍历弹出输出。
我们以char str = "8+(3-1)5"为例，8先输出，+进栈，左括号直接进栈，3输出，栈顶元素左括号"(“比减号”-"低，进栈。1直接输出，右括号时，此时栈中有“+(-”，将减号弹出并输出，最后弹出左括号。+比乘号低，进栈，5直接输出。栈中还剩乘号和加号，弹出并输出。最终中缀转后缀后应为831-5*+。
我们利用之前写过的链式栈做。
2 栈的头文件：
#ifndef SEQLINKSTACK
#define SEQLINKSTACK
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//使用企业链表实现，也可传统
typedef struct LINKSNODE{
struct LINKSNODE *next;
}LinkSNode;
//管理链表结构体
typedef struct LINKSTACK{
LinkSNode head;
int size;
}LinkStack;
//链式栈初始化
LinkStack* Init_LinkStack();
//入栈
int Push_LinkStack(LinkStack *lstack,LinkSNode *data);
//出栈
int Pop_LinkStack(LinkStack *lstack);
//判断是否为空
int IsEmpty_LinkStack(LinkStack *lstack);
//返回第一个有效元素
LinkSNode *Top_LinkStack(LinkStack *lstack);
//返回栈大小
int Size_LinkStack(LinkStack *lstack);
//清空链式栈
int Clear_LinkStack(LinkStack *lstack);
//释放内存
int Destory_LinkStack(LinkStack *lstack);
#endif
3 栈的实现.c文件：
#include"Seq_LinkStack.h"
//链式栈初始化 ok
LinkStack* Init_LinkStack(){
LinkStack *lstack=(LinkStack*)malloc(sizeof(LinkStack));
lstack->head.next=NULL;
lstack->size=0;
return lstack;
}
//入栈 ok
int Push_LinkStack(LinkStack *lstack,LinkSNode *data){
if(lstack==NULL){
return -1;
}
if(data==NULL){
return -1;
}
//每次都在链表的头结点插入,与顺序栈想反
//所以每次对头结点操作插入
data->next =lstack->head.next;
lstack->head.next=data;
lstack->size++;
return 0;
}
//出栈 ok
int Pop_LinkStack(LinkStack *lstack){
if(lstack==NULL){
return -1;
}
if(lstack->size==0){
return -1;
}
//也是只对头结点操作
//使头结点指向第二个有效节点
LinkSNode *first=lstack->head.next;
lstack->head.next=first->next; //使head指向第二个元素
lstack->size--;
return 0;
}
//判断是否为空
int IsEmpty_LinkStack(LinkStack *lstack){
if(lstack==NULL){
return -1;
}
if(lstack->size==0){
return 1;
}
return 0;
}
//返回第一个有效元素 ok
LinkSNode *Top_LinkStack(LinkStack *lstack){
if(lstack==NULL){
return NULL;
}
if(lstack->size==0){
return NULL;
}
return lstack->head.next;
}
//返回栈大小 ok
int Size_LinkStack(LinkStack *lstack){
if(lstack==NULL){
return -1;
}
return lstack->size;
}
//清空链式栈 ok
int Clear_LinkStack(LinkStack *lstack){
if(lstack==NULL){
return -1;
}
//lstack->head.next=NULL;
lstack->size=0;
return 0;
}
//释放内存
int Destory_LinkStack(LinkStack *lstack){
if(lstack==NULL){
return -1;
}
free(lstack);
return 0;
}
4 主要实现代码，前面的栈代码看不懂也没关系，直接用就行。
#include"Seq_LinkStack.h"
#include<stdio.h>
//是否为数字
int IsNumber(char p) {
return p >= '0' && p <= '9';
}
//是否为左括号
int IsLeft(char p) {
return p == '(';
}
//是否为右括号
int IsRight(char p) {
return p == ')';
}
//是否为运算符
int IsOperator(char p) {
return p == '+' || p == '-' || p == '*' || p == '/';
}
//返回运算符号优先级 左括号默认为0
int GetPriority(char c) {
if (c == '*' || c == '/') {
return 2;
}
if (c == '+' || c == '-') {
return 1;
}
return 0;
}
//链式栈数据节点
typedef struct SNODE {
LinkSNode node;
char *p;
}Snode;
void test01() {
//数字：直接输出
//左括号：直接进栈(优先级默认最低)
//右括号：将栈顶符号输出，直到匹配到左括号
//运算符：1)若一开始没有可比较直接进栈; 2)若栈顶元素优先级低，进栈; 3)若栈顶元素优先级高，将栈顶元素弹出并输出，直至低就进栈
//最后将栈中的元素遍历弹出输出
//中缀转后缀后应为831-5*+
char *str = "8+(3-1)*5";
char *p = str;
//创建栈
LinkStack *stack = Init_LinkStack();
//遍历整个字符串
while ((*p) != 0) {
//1 如果是数字 直接输出
if (IsNumber(*p)) {
printf("%c", *p);
}
//2 如果是左括号 进栈
if (IsLeft(*p)) {
Snode *data = (Snode*)malloc(sizeof(Snode));
data->p = p;
Push_LinkStack(stack, (LinkSNode*)data);
}
//3 如果是右括号 将栈中元素弹出并输出 直至遇到左括号
if (IsRight(*p)) {
while (Size_LinkStack(stack) > 0) {
Snode *tmp = (Snode*)Top_LinkStack(stack);
if (IsLeft(*(tmp->p))) {
//如果是左括号 结束并弹出左括号
Pop_LinkStack(stack);
free(tmp);
break;
}
else {
printf("%c", *tmp->p);
}
Pop_LinkStack(stack);
free(tmp);
}
}
//4 如果是运算符
//1)若一开始没有可比较直接进栈; 2)若栈顶元素优先级低，进栈; 3)若栈顶元素优先级高，将栈顶元素弹出并输出，直至低就进栈
if (IsOperator(*p)) {
//先取出栈顶元素
Snode *tmp1 = (Snode*)Top_LinkStack(stack);
//1)栈无
if (tmp1 == NULL) {
Snode *data = (Snode*)malloc(sizeof(Snode));
data->p = p;
Push_LinkStack(stack, (LinkSNode*)data);
//插入后应进行下一个字符判断 否则因tmp1为空导致下面代码出错出错
p++;
continue;
}
//2)栈低
if (GetPriority(*(tmp1->p)) < GetPriority(*p)) {
Snode *data1 = (Snode*)malloc(sizeof(Snode));
data1->p = p;
Push_LinkStack(stack, (LinkSNode*)data1);
}
//栈高
else {
while (Size_LinkStack(stack) > 0) {
//栈高输出并弹出
tmp1 = (Snode*)Top_LinkStack(stack);
if (GetPriority(*(tmp1->p)) > GetPriority(*p)) {
printf("%c", *tmp1->p);
Pop_LinkStack(stack);
free(tmp1);
}
//栈低入栈
else {
Snode *data2 = (Snode*)malloc(sizeof(Snode));
data2->p = p;
Push_LinkStack(stack, (LinkSNode*)data2);
}
}
}
}
p++;
}
//最后将栈中的元素遍历输出
while (Size_LinkStack(stack) > 0) {
Snode* tmp2 = (Snode*)Top_LinkStack(stack);
printf("%c", *tmp2->p);
Pop_LinkStack(stack);
free(tmp2);
}
//销毁栈
Destory_LinkStack(stack);
}
int main(void) {
test01();
return 0;
}
总结：总的来说，并不是很难，只要知道一开始说的四前提就可以照着写出。
