后缀表达式求值

    这是一个简单地计算后缀表达式值的代码. 使用的栈结构是用数组来实现的.

item.h

 

typedef int Item;

 

stack.h

 

struct stack
{
        Item *ptr;
        int maxnum;
        int current;
};

struct stack* stackinit(int);
int stackempty(struct stack*);
void stackpush(struct stack*, Item item);
Item stackpop(struct stack*);
void stackdestory(struct stack*);


 

arrstack.c

#include <stdio.h>
#include <stdlib.h>
#include "item.h"
#include "stack.h"


struct stack* stackinit(int maxN)
{
        struct stack* s;
        s = (struct stack*)malloc(sizeof(struct stack));
        if (s == NULL)
                return NULL;
        s->ptr = malloc(maxN * sizeof(Item));
        if (s->ptr == NULL)
        {
                free(s);
                return NULL;
        }
        s->maxnum = maxN;
        s->current = 0;
        return s;
}

int stackempty(struct stack* s)
{
        return s->current == 0;
}

void stackpush(struct stack* s, Item item)
{
        int tmp = s->current;
        if (tmp == s->maxnum)
        {
                printf("stack overflow\n");
                exit(1);
        }
        s->ptr[tmp] = item;
        s->current++;
}

Item stackpop(struct stack* s)
{
        if (s->current == 0)
        {
                printf("stack is empty\n");
                exit(1);
        }
        return s->ptr[--(s->current)];
}

void stackdestory(struct stack* s)
{
        free(s->ptr);
        free(s);
}


 

postfix.c

#include <stdio.h>
#include <string.h>
#include "item.h"
#include "stack.h"

int main(int argc, char **argv)
{
        char *a = argv[1];
        int i;
        int N = strlen(a);
        Item left, right;

        struct stack* s;
        s = stackinit(N);
        if (s == NULL)
        {
                printf("stack init error\n");
                return -1;
        }

        for (i = 0; i < N; i++)
        {
                if (a[i] == '+')
                {
                        right = stackpop(s);
                        left = stackpop(s);
                        stackpush(s, left + right);
                }
                if (a[i] == '*')
                {
                        right = stackpop(s);
                        left = stackpop(s);
                        stackpush(s, left * right);
                }
                if (a[i] == '-')
                {
                        right = stackpop(s);
                        left = stackpop(s);
                        stackpush(s, left - right);
                }
                if (a[i] == '/')
                {
                        right = stackpop(s);
                        left = stackpop(s);
                        stackpush(s, left / right);
                }
                if ((a[i] >= '0') && (a[i] <= '9'))
                {
                        stackpush(s, 0);
                        while ((a[i] >= '0') && (a[i] <= '9'))
                                stackpush(s, 10 * stackpop(s) + (a[i++] - '0'));
                        i--;
                }
        }

        printf("%d \n", stackpop(s));
        return 0;
}


编译代码:

gcc postfix.c arrstack.c -o postfix

./postfix "100 4 2 3 + * /"