定义
#define MaxSize 50
typedef struct{
ElementType data[MaxSize];
int top;
}SqStack;
定义:
typedef struct Linknode{
ElementType data;
struct Linknode *next;
}*LiStack;
功能:初始化栈
code
void initStack(SqStack &s){
s.top=-1;
}
功能:判断栈是否为空
code
bool stackEmpty(SqStack s){
if(s.top!=-1){
return false;
}else{
return true;
}
}
功能:进栈
code
bool push(SqStack &s,ElementType e){
if(s.top==MaxSize){ //判断栈满
return false;
}
s.data[++s.top]=e;
return true;
}
功能:出栈
code
bool pop(SqStack &s,ElementType &e){
if(s.top==-1){ //判断栈空
return false;
}
e=s.data[s.top--];
return true;
}
功能:获取栈顶元素
code
bool getTop(SqStack s,ElementType &e){
if(s.top==-1){
return false;
}
e=s.data[s.top];
return true;
}
定义
typedef struct{
ElementType data[MaxSize];
int front,rear;
}SqQueue;
特点:
Q.front=Q.rear定义
typedef struct{
ElementType data[MaxSize];
int front,rear;
}SqQueue;
特点:
Q.front==NULL&&Q.rear!=NULLQ.front==NULL&&Q.rear!=NULL由于队空队满条件相同的三种处理:
牺牲一个队列单元来区分队空还是队满
(Q.rear+1)%MaxSize=Q.frontQ.front==Q.rear类型中增加表示元素个数的数据成员
类型中设置tag数据成员
思想:通过多设置一个tag来区分不同状态下的队满或队空条件
tag=0,若因删除导致Q.front==Q.rear,则为队空tag=1,若因插入导致Q.front==Q.rear,则为队满定义
typedef struct{
ElementType data;
struct LinkNode *next;
}LinkNode;
typedef struct{
LinkNOde *front,*rear;
}LinkQueue;
特点:
Q.front==NULL&&Q.rear==NULL注:
LinkQueue中实际只有front和rear两个节点循环队列
功能:初始化
code
void initQueue(SqQueue &q){
q.front=0;
q.rear=0;
}
功能:判队空
code
bool isEmpty(SqQueue Q){
if(q.front==q.rear) return true;
else return false;
}
注意:循环队列下判空条件依然为q.front==q.rear
功能:入队
code
bool EnQueue(SqQueue &q,ElementType x){
if((q.rear+1)%MaxSize==q.front) return false; //验满
q.rear=(q.rear+1)%MaxSize;
q.data[q.rear]=x;
return true;
}
功能:出队
code
bool deQueue(SqQueue &q,ElementType &x){
if(q.rear==q.front) return false; //验空
x=q.data[q.front];
q.front=(q.front+1)%MaxSize;
}
链式存储
定义:初始化
code
void initQueue(LinkQueue &q){
q->front=q->rear=(LinkNode *)malloc(sizeof(LinkNOde));
q.front.next=NULL; //设置首节点的next为NULL
}
注:链式存储下的q中实际只有front和rear两个结点
定义:判队空
code
void isEmpty(LinkQueue Q){
if(q.front==q.rear) return true;
else return false;
}
定义:入队
code
void enQueue(LinkQueue &q,ElementType x){
//不用判队空
LinkNode *temp=(LinkNode *)malloc(sizeof(LinkNode));
temp->data=x;
temp->next=NULL;
q.rear->next=temp;
q.rear=q.rear->next;
}
定义:出队
code
bool deQueue(LinkQueue &q,ElementType &x){
//判空
if(q.rear==q.front) return false;
LinkNode *temp=q.front->next;
x=temp->data;
q.front=q.front->next;
if(q.rear==temp){
return true; //保持一个节点,最后一个不释放
}
free(temp);
return true;
}
规则
(,直接入栈),将运算符弹出栈直到遇到)s,根据运算符的优先级:匹配栈顶的运算符t,出栈直到遇到优先级比s低的运算符code
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <map>
using namespace std;
stack<char> s;
map<char,int> mp;
void init(){
//初始化map,定义运算符号优先级
mp[‘*‘]=2;
mp[‘/‘]=2;
mp[‘+‘]=1;
mp[‘-‘]=1;
}
string toSuffixExpression(string str){
int len=str.length();
string ans="";
for(int i=0;i<len;i++){
if(str[i]<=‘9‘&&str[i]>=‘0‘){
ans+=str[i]; //对于数值直接输出,因为对于中缀转后缀数字的相对位置不变
//cout << "num:" << str[i] << endl;
}
else if(str[i]==‘(‘){
s.push(str[i]);
}
else if(str[i]==‘)‘){
while(s.top()!=‘(‘){
ans += s.top();
s.pop();
}
s.pop();
}
else{
while(s.size()!=0&&mp[str[i]]<=mp[s.top()]){
//cout << "str:" << str[i] << endl;
//cout << "pop:" << s.top() << endl;
ans += s.top();
s.pop();
}
s.push(str[i]);
}
}
while(s.size()!=0){ //如果栈内还有运算符,追加到式子后面
ans+=s.top();
s.pop();
}
return ans;
}
int main(){
init();
string str;
cin >> str;
cout << toSuffixExpression(str);
}
注:无法将(和）使用运算符的优先级进行操作
(直接入栈,所以必然是优先级最低的运算符)必须匹配到(,如果将)设置为最低优先级的运算符,则每次遇到)必然会将栈中所有运算符都弹出原文：https://www.cnblogs.com/Arno-vc/p/14998012.html