stack.c

字符串形式的表达式求值算法

// file: stack.c
#include "stack.h"
#include "malloc.h"
#include "string.h"

// 构造一个空栈
bool InitStack(SqStack *S, uint8 elemsize)
{
    S->base = (byte *)malloc(STACK_INIT_SIZE* elemsize);
    S->elemsize = elemsize;

    if (!S->base)
        return false;

    S->top = S->base;
    S->stacksize = STACK_INIT_SIZE;
    return true;
}

// 销毁栈
void DestroyStack(SqStack *S) {free(S->base);S->base = S->top = 0;S->stacksize = 0;S->elemsize = 0;}

// 把S置为空栈
void ClearStack(SqStack *S) {S->top = S->base;}

// 判断栈是否为空
bool StackEmpty(SqStack *S) {return (S->top == S->base);}

// 返回栈的长度
int StackLength(SqStack *S) {return (S->top - S->base)/S->elemsize;}

// 若栈不空，用e返回S的栈顶元素
bool GetTop(SqStack *S, void *e) 
{
    if (StackEmpty(S) || e==0)
        return false;

    memcpy(e, (void *)(S->top-S->elemsize),S->elemsize);
    // *e = *(S->top-1);
    return true;
}

// 将e压至栈顶
bool Push(SqStack *S, void* e)
{
    if (S->top-S->base >= S->stacksize*S->elemsize)
    {
        S->base = (byte *)realloc(S,(S->stacksize + STACKINCREMENT) * S->elemsize);
        if (!S->base)
            return false;
        S->top = S->base + S->stacksize*S->elemsize;
        S->stacksize += STACKINCREMENT;
    }

    memcpy((void *)((S->top+=S->elemsize) - S->elemsize),e,S->elemsize);
    // *(S->top++) = e;
    return true;
}

// 删除栈顶元素，并以e返回
bool Pop(SqStack *S, void *e)
{
    if (StackEmpty(S))
        return false;

    S->top-=S->elemsize;
    if (e != 0)
        memcpy(e, S->top, S->elemsize);

    return true;
}

// 从栈顶到栈底（也可以栈底到栈顶）每个元素调用函数visit
// 加入方向direction，true：从底到顶 ，false：从顶到底
bool StackTraverse(SqStack *S, bool (*visit)(void* e) , bool direction)
{
    byte *pe = 0;

    if (StackEmpty(S))
        return false;

    if(direction)
    {
        pe = S->base;
        while(pe < S->top)
        {
            if (!visit((pe+=S->elemsize) - S->elemsize))return false;
        }
    }
    else
    {
        pe = S->top;
        while(pe >= S->base)
        {
            if (!visit(pe-=S->elemsize))return false;
        }
    }

    return true;
}