睿达科网络 网站建设,成都网站建设推广在,用canvas做网站,wordpress 虚拟币**中缀表达式转后缀表达式的一般步骤如下#xff1a; 1#xff1a;创建一个空的栈和一个空的输出列表。 2#xff1a;从左到右扫描中缀表达式的每个字符。 3#xff1a;如果当前字符是操作数#xff0c;则直接将其加入到输出列表中。 4#xff1a;如果当前字符是运算符 1创建一个空的栈和一个空的输出列表。 2从左到右扫描中缀表达式的每个字符。 3如果当前字符是操作数则直接将其加入到输出列表中。 4如果当前字符是运算符比较其与栈顶运算符的优先级 a. 如果栈为空或栈顶运算符是左括号(“则直接将当前运算符入栈。 b. 如果当前运算符的优先级高于栈顶运算符的优先级则将当前运算符入栈。 c. 如果当前运算符的优先级低于或等于栈顶运算符的优先级则将栈顶运算符弹出并加入到输出 列表中 直到栈为空或栈顶运算符的优先级低于当前运算符的优先级然后将当前运算符入栈。 d. 如果当前字符是右括号”)“则依次弹出栈中的运算符并加入到输出列表中 直到遇到左括号”(为止此时将左括号出栈且不加入输出列表。 5扫描完整个中缀表达式后将栈中剩余的运算符依次弹出并加入到输出列表中。 6输出列表即为转换后的后缀表达式。 举个例子 中缀表达式2 3 * (4 - 1) 转换为后缀表达式2 3 4 1 - * 具体实现需要根据编程语言和数据结构来进行操作。**
项目结构 项目头文件结构QueueStorage.h 项目头文件代码
#ifndef LINKSTACK_H
#define LINKSTACK_H
#include stdio.h
#include stdlib.h
// 链式栈的节点
typedef struct LINKNODE {struct LINKNODE* next;
}LinkNode;
// 链式栈
typedef struct LINKSTACK {LinkNode head;int size;}LinkStack;// 初始化函数
LinkStack* Init_LinkStack();
// 入栈
void Push_LinkStack(LinkStack* stack, LinkNode* data);
// 出栈
void Pop_LinkStack(LinkStack* stack);
// 返回栈顶元素
LinkNode* TopLinkStack(LinkStack* stack);
// 返回栈元素的个数
int Size_LinkStack(LinkStack* stack);
// 清空栈
void Clear_LinkStack(LinkStack* stack);
// 销毁栈
void FreeSpace_LinkStack(LinkStack* stack);
#endif项目cpp文件QueueStorage.cpp 项目cpp文件代码QueueStorage.cpp
#define _CRT_SECURE_NO_WARNINGS
#include stdio.h
#include stdlib.h
#include math.h
#include iostream
#include string.h
#include QueueStorage.h// 初始化函数
LinkStack* Init_LinkStack() {LinkStack* stack (LinkStack*)malloc(sizeof(LinkStack));stack-head.next NULL;stack-size 0;return stack;
};
// 入栈
void Push_LinkStack(LinkStack* stack, LinkNode* data) {if (stack NULL) {return;}if (data NULL) {return;}// 入栈data-next stack-head.next;stack-head.next data;stack-size;
};
// 出栈
void Pop_LinkStack(LinkStack* stack) {if (stack NULL) {return;}if (stack-size 0) {return;}// 第一个有效节点LinkNode* pNext stack-head.next;stack-head.next pNext-next;stack-size--;};
// 返回栈顶元素
LinkNode* TopLinkStack(LinkStack* stack) {if (stack NULL) {return NULL;}if (stack-size 0) {return NULL;}// 返回栈顶元素return stack-head.next;
};// 返回栈元素的个数
int Size_LinkStack(LinkStack* stack) {if (stack NULL) {return -1;}return stack-size;
};
// 清空栈
void Clear_LinkStack(LinkStack* stack) {if (stack NULL) {return;}// 清空栈stack-head.next NULL;stack-size 0;};
// 销毁栈
void FreeSpace_LinkStack(LinkStack* stack) {if (stack NULL) {return;}free(stack);
};项目主文件截图 项目主文件代码main.cpp
#define _CRT_SECURE_NO_WARNINGS
#include stdio.h
#include stdlib.h
#include math.h
#include iostream
#include string.h
#include QueueStorage.hint IsNumber(char c) {return c 0 c 9;
}
// 判断是不是左括号
int IsLeft(char c) {return c (;
}
// 判断是不是右括号
int IsRight(char c) {return c );
}
// 判断是不是运算符号
int IsOperator(char c) {return c || c - || c * || c /;
}
//返回运算符号的优先级
int GetPriority(char c) {if (c * || c /) {return 2;}if (c || c -) {return 1;}return 0;
}//使用企业链表的方式进行实现需要添加结构体
typedef struct MYCHAR {LinkNode node;char* p;}MyChar;// 对于数字的操作
void NumberOperate(char* p) {printf(%c, *p);
}
// 创建MyChar
MyChar* CreateMyChar(char* p) {MyChar* mychar (MyChar*)malloc(sizeof(MyChar));mychar-p p;return mychar;
}// 对于左括号的操作
void LeftOperate(LinkStack* stack,char* p) {Push_LinkStack(stack, (LinkNode*)CreateMyChar(p));
}
// 对于右括号的操作
void RightOperate(LinkStack* stack) {// 判断栈中是否存在元素while (Size_LinkStack(stack) 0) {// 将里面的元素取出MyChar* mychar (MyChar*)TopLinkStack(stack);// 如果匹配到左括号的话就弹出if (IsLeft(*(mychar-p))) {Pop_LinkStack(stack);break;}// 输出printf(%c, *(mychar-p));// 弹出Pop_LinkStack(stack);// 释放内存free(mychar);}
}
// 运算符号的操作
void OperatorOperate(LinkStack* stack, char* p) {// 取出栈顶符号MyChar* mychar (MyChar*)TopLinkStack(stack);if (mychar NULL) {Push_LinkStack(stack, (LinkNode*)CreateMyChar(p));return;}// 如果栈顶优先级低于符号的优先级直接入栈if (GetPriority(*(mychar-p) GetPriority(*p))) {Push_LinkStack(stack,(LinkNode*)CreateMyChar(p));return;}else {// 如果栈顶符号优先级不低while (Size_LinkStack(stack) 0) {MyChar* mychar2 (MyChar*)TopLinkStack(stack);// 如果优先级低当前的符号入栈if (GetPriority(*(mychar2-p)) GetPriority(*p)) {Push_LinkStack(stack, (LinkNode*)CreateMyChar(p));break;}// 输出printf(%c , *(mychar2-p));// 弹出Pop_LinkStack(stack);// 释放free(mychar2);}}
}int main()
{/*栈的应用中缀表达式转后缀表达式*/char* str (char *)8 (3 - 1) * 5;// 遍历字符串char* p str;// 创建栈LinkStack* stack Init_LinkStack();while (*p ! \0) {// 判断是否数数字如果是数字的话直接输出if (IsNumber(*p)) {NumberOperate(p);}// 判断是不是左括号如果是左括号直接进栈if (IsLeft(*p)) {LeftOperate(stack,p);}// 如果是右括号的话将栈顶符号弹出知道匹配到左括号为止if (IsRight(*p)) {RightOperate(stack);}// 如果是运算符号的话if (IsOperator(*p)) {OperatorOperate(stack,p);}p;}//将栈中剩余的元素弹出并输出while (Size_LinkStack(stack) 0) {MyChar* mychar (MyChar*)TopLinkStack(stack);printf(%c, *(mychar-p));Pop_LinkStack(stack);free(mychar);}system(pause);return 0;
}修改运行界面 项目运行结果 后缀表达式相关原理
计算这个后缀表达式2 3 4 1 - * 。**
首先我们从左到右扫描后缀表达式遇到数字就将其入栈遇到运算符则将栈顶的两个数字弹出进行计算然后将结果入栈。 具体计算过程如下
将2和3入栈遇到4入栈遇到1入栈遇到减号-弹出栈顶两个数字1和4计算4-13将结果3入栈遇到乘号弹出栈顶两个数字3和3计算339将结果9入栈遇到加号弹出栈顶两个数字9和2计算9211将结果11入栈后缀表达式扫描结束栈顶的数字11即为最终的计算结果。
主文件 主文件截图 主文件代码
#define _CRT_SECURE_NO_WARNINGS
#include stdio.h
#include stdlib.h
#include math.h
#include iostream
#include string.h
#include QueueStorage.hint IsNumber2(char c) {return c 0 c 9;
}
typedef struct MYNUM{LinkNode node;int val;}MyNum;
int Calculate(int left,int right,char c) {int ret 0;switch (c) {case :ret left right;break;case -:ret left - right;break;case *:ret left * right;break;case /:ret left / right;break;default:break;}return ret;
}int main(void) {/*根据后缀表达式求解*/char* str (char *)831-5*;char* p str;// 创建栈LinkStack* stack Init_LinkStack();// 对后缀表达式进行扫描while (*p ! \0) {// 如果是数字直接入栈if (IsNumber2(*p)) {MyNum* num (MyNum*)malloc(sizeof(MyNum));num-val *p - 0;Push_LinkStack(stack,(LinkNode*)num);}else {MyNum* right (MyNum*)TopLinkStack(stack);// 如果是运算符的话先从栈中弹出右操作数int rightNum right-val;Pop_LinkStack(stack);free(right);// 取出左操作数MyNum* left (MyNum*)TopLinkStack(stack);int leftNum left-val;Pop_LinkStack(stack);free(left);int ret Calculate(leftNum, rightNum, *p);// 结果入栈MyNum* num (MyNum*)malloc(sizeof(MyNum));num-val ret;Push_LinkStack(stack, (LinkNode*)num);}p;}if (Size_LinkStack(stack) 1) {MyNum* num (MyNum*)TopLinkStack(stack);printf(运算结果是%d\n, num-val);Pop_LinkStack(stack);free(num);}// 释放栈FreeSpace_LinkStack(stack);system(pause);return 0;
}运行结果展示
