计算器实例
main.c
#include <stdlib.h>
#include <stdio.h>
#include "sqstack.h"
void compute(sqstack* snum,datatype* data)
{
datatype n1,n2,n;
st_pop(snum,&n2);
st_pop(snum,&n1);
switch(*data)
{
case '+':
n = n1 +n2;
break;
case '-':
n = n1 - n2;
break;
case '*':
n = n1 * n2;
break;
case '/':
n = n1 / n2;
break;
default:
exit(1);
break;
}
st_push(snum,&n);
}
int get_pri(int op)
{
switch(op)
{
case '(':
return 0;
case '+':
return 1;
case '-':
return 1;
case '*':
case '/':
return 2;
}
}
void deal_bracket(sqstack*snum ,sqstack* sop)
{
datatype old_op;
st_top(sop,&old_op);
while(old_op != '(')
{
st_pop(sop,&old_op);
compute(snum,&old_op);
st_top(sop,&old_op);
}
st_pop(sop,&old_op); //弹出左括号
}
void deal_op(sqstack*snum,sqstack*sop,int op)
{
datatype old_op;
if( (st_isempty(sop)==0) ||op =='(' )
{
st_push(sop,&op);
return ;
}
st_top(sop,&old_op);
if(get_pri(op) > get_pri(old_op))
{
st_push(sop,&op);
return;
}
while( get_pri(op) <= get_pri(old_op) )
{
st_pop(sop,&old_op);
compute(snum,&old_op);
if(st_isempty(sop)== 0)
break;
st_top(sop,&old_op);
}
st_push(sop,&op);
}
int main()
{
datatype old_op;
int i=0;
int value =0;
int flag = 0;
char str[] = "(11+3)*2-5"; //23
sqstack*snum,*sop;
snum = st_create();
sop = st_create();
while(str[i] != '\0')
{
// printf("%c \n",str[i]);
// num
if(str[i]> '0' && str[i]< '9' )
{
value = value*10 + (str[i]- '0') ; //求差值,原来内容移位
flag = 1;
}
else // op
{
if(flag == 1) //证明取过了数值
{
st_push(snum,&value);
value = 0;
flag = 0;
}
if(str[i]==')')
{
deal_bracket(snum,sop);
}
else // 可能是 ( + - * /
{
deal_op(snum,sop,str[i]);
}
}
i++;
}
if(flag) //最后一个元素
{
st_push(snum,&value);
}
st_travel(snum);
printf("--------\n");
while(!(st_isempty(sop)==0) )
{
st_pop(sop,&old_op);
compute(snum,&old_op);
if(st_isempty(sop)==0)
break;
st_top(sop,&old_op);
}
st_travel(snum);
st_destroy(snum);
st_destroy(sop);
return 0;
}
sqstack.h
#ifndef SQSTACK_H
#define SQSTACK_H
#define MAXSIZE 32
typedef int datatype;
typedef struct node_st
{
datatype data[MAXSIZE];
int top;
}sqstack;
sqstack* st_create(void);
int st_isempty(sqstack*);
int st_push(sqstack*,datatype*);
int st_pop(sqstack*,datatype*);
int st_top(sqstack*,datatype*);
void st_travel(sqstack*);
int st_destroy(sqstack*);
#endif
sqstack.c
#include <stdlib.h>
#include <stdio.h>
#include "sqstack.h"
sqstack* st_create(void)
{
sqstack*st;
st = malloc(sizeof(*st));
if(st == NULL)
return NULL;
st->top = -1;
return st;
}
int st_isempty(sqstack*st)
{
if(st->top == -1)
return 0;
return 1;
// return (st->top == -1);
}
int st_push(sqstack*st,datatype* data)
{
if(st->top == MAXSIZE-1 )
return -1;
st->data[++st->top] = *data;
return 0;
}
int st_pop(sqstack*st,datatype*data)
{
if(st_isempty(st)==0)
return -1;
*data = st->data[st->top--];
return 0;
}
int st_top(sqstack*st,datatype*data)
{
if(st_isempty(st )== 0)
return -1;
*data = st->data[st->top];
return 0;
}
void st_travel(sqstack*st)
{
if(st_isempty(st)== 0)
return;
for(int i=0;i<=st->top;i++)
{
printf("%d ",st->data[i]);
}
printf("\n");
}
int st_destroy(sqstack*st)
{
free(st);
st = NULL;
return 0;
}
球钟算法
代码中包含的sqstack.h/sqstack.c和 queue.h/queue.c参考之前文章：C数据结构栈，C数据结构队列，采用的是顺序存储栈，顺序存储队列，如有疑问，可以给博主留言。
main.c
#include <stdlib.h>
#include <stdio.h>
#include "sqstack.h"
#include "queue.h"
#define BALL_SIZE 27
static int check(queue*qu)
{
int i = (qu->head+1)%MAXSIZE;
while(i != qu->tail )
{
if(qu->data[i] > qu->data[(i+1)%MAXSIZE ])
return 0;
i = (i+1)%MAXSIZE;
}
return 1;
}
int main()
{
int t,time = 0;
queue* qu;
int value = 0;
sqstack*st_min,*st_fivemin,*st_hour;
qu = qu_create();
st_min = st_create();
st_fivemin = st_create();
st_hour = st_create();
for(int i=1;i<=BALL_SIZE;i++)
{
qu_enqueue(qu,&i);
}
qu_travel(qu);
while(1)
{
qu_dequeue(qu,&t);
time++;
if(st_min->top != 3)
{
st_push(st_min,&t);
}
else
{
while(st_isempty(st_min)!=0)
{
st_pop(st_min,&value);
qu_enqueue(qu,&value);
}
if(st_fivemin->top !=10)
{
st_push(st_fivemin,&t);
}
else
{
while(st_isempty(st_fivemin)!=0 )
{
st_pop(st_fivemin,&value);
qu_enqueue(qu,&value);
}
if(st_hour->top != 10)
{
st_push(st_hour,&t);
}
else
{
while(st_isempty(st_hour) !=0 )
{
st_pop(st_hour,&value);
qu_enqueue(qu,&value);
}
qu_enqueue(qu,&t);
if(check(qu))
break;
}
}
}
}
printf("time = %d \n",time);
qu_destroy(qu);
st_destroy(st_min);
st_destroy(st_fivemin);
st_destroy(st_hour);
return 0;
}
补充
大家也可以把上面用到的stack.h/llist.h两个文件编译为动态库使用。注意：
gcc -shared -fpic -o libstack_s.so stack.c
gcc main.c -o all -lstack_s -lllist_s
库之间有依赖关系，前面的动态库依赖于后面的stack_s中用到了llist
