栈——实验及提升训练
- 参考链接：https://www.cnblogs.com/blogxjc/p/11287961.html，https://www.cnblogs.com/Roni-i/p/8586332.html，https://www.cnblogs.com/lanhaicode/p/10776166.html
#include
#include // 自己定义需要的栈结构，及栈基本操作函数，假设操作数都是整数 #define maxn 100005 typedef int DataType ; struct stack { DataType data[maxn]; }; /*在此定义并完成第一关函数，参考main要求*/ int result(int n,int m,int a,int x)//分别表示n站，最后一站下车的人数m，始发站上车人数a，求第x站时车上的人数 { struct stack pstack; pstack.data[1]=1; pstack.data[2]=1; for (int i = 3; i <=n ; ++i) { pstack.data[i]=pstack.data[i-1]+pstack.data[i-2]; } DataType ans; ans=(m-(pstack.data[n-3]+1)*a)/(pstack.data[n-2]-1); ans=(pstack.data[x-2]+1)*a+(pstack.data[x-1]-1)*ans; return ans; } 头文件
#include
#include #include "stack.h" int main() { int n,m,a,x ;//分别表示n站，最后一站下车的人数m，始发站上车人数a，求第x站时车上的人数 scanf("%d%d%d%d",&n,&m,&a,&x); printf("%d",result(n,m,a,x)); } 主函数
第2关：中缀表达式转换为后缀表达式
1 #define _CRT_SECURE_NO_WARNINGS 2 #include
第2关：中缀表达式转换为后缀表达式3 #include 4 #include <string.h> 5 6 #define STACK_INIT_SIZE 20 7 #define STACK_INCREMENT 10 8 #define EXPRESS_MAX 10274 9 typedef char element; 10 typedef int status; 11 typedef struct stack 12 { 13 element *top; 14 element *base; 15 int stackSize; 16 char ch[100]; 17 }Stack; 18 status initStack(Stack *stack) 19 { 20 stack->base=stack->top=(element*)malloc(sizeof(Stack)*STACK_INIT_SIZE); 21 if(!stack->base) 22 { 23 exit(0); 24 } 25 stack->stackSize=STACK_INIT_SIZE; 26 return 1; 27 } 28 status push(Stack *stack,element e) 29 { 30 if(stack==NULL) 31 { 32 return 0; 33 } 34 if(stack->top - stack->base == stack->stackSize) 35 { 36 stack->base=(element*)realloc(stack->base,stack->stackSize+STACK_INCREMENT); 37 if(!stack->base) 38 { 39 exit(0); 40 41 } 42 stack->top=stack->base+stack->stackSize; 43 stack->stackSize+=STACK_INCREMENT; 44 } 45 *stack->top=e; 46 stack->top++; 47 return 1; 48 } 49 status pop(Stack* stack,element *e) 50 { 51 if(stack==NULL||e==NULL) 52 { 53 return 0; 54 } 55 if(stack->top==stack->base) 56 { 57 return 0; 58 } 59 *stack->top--; 60 *e=*stack->top; 61 return 1; 62 } 63 64 status getTop(Stack *stack,element *e)//get the stack element to e 65 { 66 if(NULL==stack) 67 { 68 return 0; 69 } 70 *e = *(stack->top-1); 71 return 1; 72 } 73 74 status isEmptyStack(Stack *stack)//negative for emp,posative for emp,0 for exi 75 { 76 if(NULL==stack) 77 { 78 return -1; 79 } 80 if(stack->top==stack->base) 81 { 82 return 1; 83 } 84 return 0; 85 } 86 status DestroyStack(Stack *stack) 87 { 88 if(NULL==stack) 89 { 90 return 0; 91 } 92 if(!stack->base) 93 { 94 free(stack->base); 95 } 96 stack->top=stack->base=NULL; 97 stack->stackSize=0; 98 return 1; 99 100 } 101 102 Stack inToPost(char *expression) 103 { 104 //在此处填写代码，完成中缀表达式转换为后缀表达式并输出 105 /********** Begin **********/ 106 107 char *suffixExp=(char*)malloc(sizeof(char)*EXPRESS_MAX); 108 memset(suffixExp,0,EXPRESS_MAX); 109 110 111 int indexSuf=0; 112 int indexPre=0; 113 Stack symbolStack; 114 initStack(&symbolStack); 115 116 char numLen[10]={0}; 117 char ch = 0; 118 int numLenIndex=0;//index of numLen arrray 119 while(expression[indexPre]) 120 { 121 ch=expression[indexPre++]; 122 if(ch==' ') 123 { 124 continue; 125 } 126 if ('\0'==ch) 127 { 128 break; 129 } 130 if (ch>='0'&&ch<='9')//exp is digital 131 { 132 while ((('0'<=ch&&'9'>=ch)||'.'==ch) && numLenIndex < 10)//continuous number 133 { 134 numLen[numLenIndex++]=ch; 135 suffixExp[indexSuf++]=ch; 136 ch=expression[indexPre++]; 137 } 138 numLen[numLenIndex]=0; 139 suffixExp[indexSuf++]=' '; 140 } 141 if('\0'==ch) 142 { 143 break; 144 } 145 else if (' '==ch) 146 { 147 continue; 148 } else if(ch<'0'||ch>'9')//not digital 149 { 150 numLenIndex=0; 151 if (')'==ch) 152 { 153 int flag=1; 154 while (!isEmptyStack(&symbolStack)) 155 { 156 pop(&symbolStack,&ch); 157 if('('==ch) 158 { 159 flag=0; 160 break; 161 } 162 suffixExp[indexSuf++]=ch; 163 suffixExp[indexSuf++]=' '; 164 } 165 if(flag) 166 { 167 printf("wrong input\n"); 168 exit(0); 169 } 170 }else if ('+'==ch||'-'==ch) 171 { 172 element top; 173 getTop(&symbolStack,&top); 174 if(isEmptyStack(&symbolStack)||'('==top) 175 { 176 push(&symbolStack,ch); 177 }else{ 178 char cur =ch; 179 while(!isEmptyStack(&symbolStack)) 180 { 181 pop(&symbolStack,&ch); 182 if ('('==ch) 183 { 184 push(&symbolStack,ch); 185 break; 186 } 187 suffixExp[indexSuf++]=ch; 188 suffixExp[indexSuf++]=' '; 189 190 } 191 push(&symbolStack,cur); 192 193 } 194 } 195 else if('*'==ch||'/'==ch) 196 { 197 element top; 198 getTop(&symbolStack,&top); 199 if (isEmptyStack(&symbolStack)||'('==top||'-'==top||'+'==top) 200 { 201 push(&symbolStack,ch); 202 }else if ('*'==top||'/'==top) 203 { 204 char cur=ch; 205 while (!isEmptyStack(&symbolStack)) 206 { 207 pop(&symbolStack,&ch); 208 if('('==ch||'-'==ch||'+'==ch) 209 { 210 push(&symbolStack,ch); 211 break; 212 } 213 suffixExp[indexSuf++]=ch; 214 suffixExp[indexSuf++]=' '; 215 216 } 217 push(&symbolStack,cur); 218 } 219 } 220 else if ('('==ch) 221 { 222 push(&symbolStack,ch); 223 } else 224 { 225 printf("wrong input\n"); 226 exit(0); 227 } 228 } 229 } 230 231 while (!isEmptyStack(&symbolStack)) 232 { 233 pop(&symbolStack,&ch); 234 suffixExp[indexSuf++]=ch; 235 suffixExp[indexSuf++]=' '; 236 237 } 238 suffixExp[indexSuf]='\n'; 239 Stack ans; 240 initStack(&ans); 241 int i; 242 for ( i = 0; suffixExp[i]!='\n'; ++i) { 243 ans.ch[i]=suffixExp[i]; 244 } 245 ans.ch[i]='\n'; 246 return ans; 247 248 /********** End **********/ 249 } 250 251 //print函数用于输出后缀表达式，参数是 inToPost的返回值 252 253 void print(Stack s) 254 { 255 for (int i = 0; s.ch[i]!='\n'; ++i) { 256 printf("%c",s.ch[i]); 257 } 258 259 260 } -
#define _CRT_SECURE_NO_WARNINGS #include
#include #include <string.h> #include #define MAX 100 #define STACK_INIT_SIZE 20 #define STACK_INCREMENT 10 #define EXPRESS_MAX 10274 void CalculateAndPush(double *num, int *i, int *j, char mm); double transCharToDouble(char *c,int exp); typedef char element; typedef int status; typedef struct stack { element *top; element *base; int stackSize; char ch[100]; }Stack; status initStack(Stack *stack) { stack->base=stack->top=(element*)malloc(sizeof(Stack)*STACK_INIT_SIZE); if(!stack->base) { exit(0); } stack->stackSize=STACK_INIT_SIZE; return 1; } status push(Stack *stack,element e) { if(stack==NULL) { return 0; } if(stack->top - stack->base == stack->stackSize) { stack->base=(element*)realloc(stack->base,stack->stackSize+STACK_INCREMENT); if(!stack->base) { exit(0); } stack->top=stack->base+stack->stackSize; stack->stackSize+=STACK_INCREMENT; } *stack->top=e; stack->top++; return 1; } status pop(Stack* stack,element *e) { if(stack==NULL||e==NULL) { return 0; } if(stack->top==stack->base) { return 0; } *stack->top--; *e=*stack->top; return 1; } status getTop(Stack *stack,element *e)//get the stack element to e { if(NULL==stack) { return 0; } *e = *(stack->top-1); return 1; } status isEmptyStack(Stack *stack)//negative for emp,posative for emp,0 for exi { if(NULL==stack) { return -1; } if(stack->top==stack->base) { return 1; } return 0; } status DestroyStack(Stack *stack) { if(NULL==stack) { return 0; } if(!stack->base) { free(stack->base); } stack->top=stack->base=NULL; stack->stackSize=0; return 1; } Stack inToPost(char *expression) { //在此处填写代码，完成中缀表达式转换为后缀表达式并输出 /********** Begin **********/ char *suffixExp=(char*)malloc(sizeof(char)*EXPRESS_MAX); memset(suffixExp,0,EXPRESS_MAX); int indexSuf=0; int indexPre=0; Stack symbolStack; initStack(&symbolStack); char numLen[10]={0}; char ch = 0; int numLenIndex=0;//index of numLen arrray while(expression[indexPre]) { ch=expression[indexPre++]; if(ch==' ') { continue; } if ('\0'==ch) { break; } if (ch>='0'&&ch<='9')//exp is digital { while ((('0'<=ch&&'9'>=ch)||'.'==ch) && numLenIndex < 10)//continuous number { numLen[numLenIndex++]=ch; suffixExp[indexSuf++]=ch; ch=expression[indexPre++]; } numLen[numLenIndex]=0; suffixExp[indexSuf++]=' '; } if('\0'==ch) { break; } else if (' '==ch) { continue; } else if(ch<'0'||ch>'9')//not digital { numLenIndex=0; if (')'==ch) { int flag=1; while (!isEmptyStack(&symbolStack)) { pop(&symbolStack,&ch); if('('==ch) { flag=0; break; } suffixExp[indexSuf++]=ch; suffixExp[indexSuf++]=' '; } if(flag) { printf("wrong input\n"); exit(0); } }else if ('+'==ch||'-'==ch) { element top; getTop(&symbolStack,&top); if(isEmptyStack(&symbolStack)||'('==top) { push(&symbolStack,ch); }else{ char cur =ch; while(!isEmptyStack(&symbolStack)) { pop(&symbolStack,&ch); if ('('==ch) { push(&symbolStack,ch); break; } suffixExp[indexSuf++]=ch; suffixExp[indexSuf++]=' '; } push(&symbolStack,cur); } } else if('*'==ch||'/'==ch) { element top; getTop(&symbolStack,&top); if (isEmptyStack(&symbolStack)||'('==top||'-'==top||'+'==top) { push(&symbolStack,ch); }else if ('*'==top||'/'==top) { char cur=ch; while (!isEmptyStack(&symbolStack)) { pop(&symbolStack,&ch); if('('==ch||'-'==ch||'+'==ch) { push(&symbolStack,ch); break; } suffixExp[indexSuf++]=ch; suffixExp[indexSuf++]=' '; } push(&symbolStack,cur); } } else if ('('==ch) { push(&symbolStack,ch); } else { printf("wrong input\n"); exit(0); } } } while (!isEmptyStack(&symbolStack)) { pop(&symbolStack,&ch); suffixExp[indexSuf++]=ch; suffixExp[indexSuf++]=' '; } suffixExp[indexSuf]='\n'; Stack ans; initStack(&ans); int i; for ( i = 0; suffixExp[i]!='\n'; ++i) { ans.ch[i]=suffixExp[i]; } ans.ch[--i]='\n'; return ans; /********** End **********/ } //print函数用于输出后缀表达式，参数是 inToPost的返回值 void print(Stack s) { for (int i = 0; s.ch[i]!='\n'; ++i) { printf("%c",s.ch[i]); } } int calExp(char *express) { Stack s =inToPost(express); //char ss[MAX]; double num[MAX]={0};//stack int j=0; int i=0; int flagIsConNum=1; for ( ; s.ch[i]!='\n'; ) { //is num if (s.ch[i]>= '0' && s.ch[i] <= '9') { flagIsConNum=1; char numCon[10]; int numIndex=0; numCon[numIndex++]=s.ch[i++]; //1.continuos num if (s.ch[i]>= '0' && s.ch[i] <= '9') { flagIsConNum=0; while (s.ch[i]>= '0' && s.ch[i] <= '9') { numCon[numIndex++]=s.ch[i++]; // i++; } numCon[numIndex]='\n'; //int copNumIndex=numIndex; num[j++]=transCharToDouble(numCon,numIndex); /* while (numIndex>cnt) { num[j]+= (double)(numCon[--copNumIndex] - '0') * pow(10, cnt); cnt++; } */ } //2.not continuous num if (flagIsConNum) { num[j++]=(double)(s.ch[i-1]-'0'); } }else if (' '==s.ch[i]) { i++; } else if (s.ch[i] == '+' || s.ch[i] == '-' || s.ch[i] == '*' || s.ch[i] == '/') { CalculateAndPush(num,&i,&j,s.ch[i]); }else if (s.ch[i]=='\n') { break; } } return (int)num[0]; } void CalculateAndPush(double *num, int *i, int *j, char mm) { switch (mm) { case '+': { num[(*j)-2]=num[(*j)-1]+num[(*j)-2]; (*j)--; (*i)++; break; } case '-': { num[(*j)-2]=num[(*j)-2]-num[(*j)-1]; (*j)--; (*i)++; break; } case '*': { num[(*j)-2]=num[(*j)-1]*num[(*j)-2]; (*j)--; (*i)++; break; } case '/': { num[(*j)-2]=num[(*j)-2]/num[(*j)-1]; (*j)--; (*i)++; break; } default:exit(0); } } double transCharToDouble(char *c,int exp) { double ret=0; int i=0; while (c[i++]!='\n'&&exp>=0) { ret+=(double)(c[--exp]-'0')*pow(10,i-1); } return ret; }