“Linkstack.h”
#pragma once typedef int Elemtype; typedef struct _Node { Elemtype data; char ptr; struct _Node* next; }Node; typedef struct _Linkstack { Node head; }Linkstack,*ptrstack; //初始化 void init(ptrstack stack); //入栈1 void Push(ptrstack stack,int val); //出栈1 void Pop(ptrstack stack,int *val); //入栈2 void Push1(ptrstack stack,char ptr); //出栈2 void Pop1(ptrstack stack,char *ptr); //清空 void clear(ptrstack stack); //销毁 void destroy(ptrstack stack); //后缀表达式求值 int RPN_num(ptrstack stack,char *str); //中缀转后缀 void RPN_change(ptrstack stack,char *str,char *brr);.cpp
#include"Linkstack.h" #include<stdio.h> #include<string.h> #include<stdlib.h> #include<assert.h> #include<malloc.h> #include<ctype.h> void init(ptrstack stack) { assert(stack!=NULL); if(stack==NULL) { return; } stack->head.next=NULL; } void Push(ptrstack stack,int val) { assert(stack!=NULL); if(stack==NULL) { return ; } Node* newnode=(Node*)malloc(sizeof(Node)); newnode->data=val; newnode->next=stack->head.next; stack->head.next=newnode; } void Pop(ptrstack stack,int *val) { assert(stack!=NULL); if(stack==NULL) { return ; } if(stack->head.next==NULL) { return ; } Node* q=stack->head.next; *val=q->data; stack->head.next=q->next; free(q); q=NULL; } void Push1(ptrstack stack,char ptr) { assert(stack!=NULL); if(stack==NULL) { return ; } Node* newnode=(Node*)malloc(sizeof(Node)); newnode->ptr=ptr; newnode->next=stack->head.next; stack->head.next=newnode; } void Pop1(ptrstack stack,char *ptr) { assert(stack!=NULL); if(stack==NULL) { return ; } if(stack->head.next==NULL) { return ; } Node* q=stack->head.next; *ptr=q->ptr; stack->head.next=q->next; free(q); q=NULL; }例如：9 + ( 3 - 1 )* 10+ 10 / 2 —> 9 3 1 - 10 * + 10 2 / + 思想： 1.循环遍历字符串： （1）遇到数字或者空格就直接输出（这里输出是指将其保存在额外给的数组里） （2）否则： 遇到加减：如果栈为空就压栈，不为空则判断与栈顶元素的优先级，因为加减小于乘除，而且同级别也需要输出的关系，即只要栈顶元素为加减乘除的任意一个，就循环出栈并输出，直到栈为空。 遇到乘除或者左括号，就直接压栈。 遇到右括号，就将栈中元素依次出栈并输出，直到遇到左括号。同时再将左括号出栈。 2.遍历结束之后，因为栈中可能依然有元素的关系，我们需要依次出栈并输出。
void RPN_change(ptrstack stack,char *str,char *brr) { assert(stack!=NULL&&str!=NULL); if(stack==NULL||str==NULL) { return ; } int i=0,j=0; char p; while(str[i]!='\0') { if(isdigit(str[i])) { brr[j++]=str[i]; i++; } else if(str[i]==' ') { brr[j++]=str[i++]; } else { if(str[i]=='+'||str[i]=='-') { Node *q=stack->head.next; if(stack->head.next==NULL) { Push1(stack,str[i]); } else { if(q->ptr=='/'||q->ptr=='+'||q->ptr=='-'||q->ptr=='*') { while(stack->head.next!=NULL) { Pop1(stack,&brr[j++]); } } Push1(stack,str[i]); } } else if(str[i]==')') { while(stack->head.next->ptr!='(') { Pop1(stack,&brr[j++]); } Pop1(stack,&p); } else if(str[i]=='*'||str[i]=='/'||str[i]=='(') { Push1(stack,str[i]); } i++; } } while(stack->head.next!=NULL) { Pop1(stack,&brr[j++]); } brr[j]='\0'; }思想： 1.循环遍历字符串： （1）遇到数字就直接压栈；因为是字符的关系，为了以免而会将原先一个数字字符分成两个字符，需要用一个标记记录当前这个是数字并保存值，下一次循环再次遇到数字时，就用保存的值*10+当前的数字。 （2）遇到空格就直接输出。 （3）遇到符号就将栈顶的两个元素出栈，第一个作为right，第二个作为left，然后将他们计算得出的值压栈。
int RPN_num(ptrstack stack,char *str) { assert(stack!=NULL&&str!=NULL); if(stack==NULL||str==NULL) { return NULL; } int num=0; int i=0; int left,right; int flg=-1,count=0; while(str[i]!='\0') { if(isdigit(str[i])) { if(flg==-1) { count=(str[i]-'0'); Push(stack,count); flg=1; i++; } else if(flg==1) { count=count*10+(str[i]-'0'); Pop(stack,&left); Push(stack,count); i++; flg=1; } } else if(str[i]=='+') { Pop(stack,&right); Pop(stack,&left); Push(stack,left+right); count=0; flg=-1; i++; } else if(str[i]=='-') { Pop(stack,&right); Pop(stack,&left); Push(stack,left-right); count=0; flg=-1; i++; } else if(str[i]=='*') { Pop(stack,&right); Pop(stack,&left); Push(stack,left*right); count=0; flg=-1; i++; } else if(str[i]=='/') { Pop(stack,&right); Pop(stack,&left); Push(stack,left/right); count=0; flg=-1; i++; } else if(str[i]==' ') { count=0; flg=-1; i++; } } Pop(stack,&num); return num; }测试
Linkstack p; init(&p); char str[]="9 + ( 3 - 1 ) * 10 + 10 / 2"; char *brr=new char[strlen(str)+1](); RPN_change(&p,str,brr); printf("%s\n",brr); //char str[]="9 3 1- 3 * + 10 2 / +"; int num=RPN_num(&p,brr); printf("%d\n",num);