返回顶部

收藏

C语言通过堆栈计算逆波兰式

更多
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Mystack *Stack;

struct Mystack {
    int Capacity;       /* 栈的容量 */
    int Top_of_stack;   /* 栈顶下标 */
    int *Array;     /* 存放栈中元素的数组 */
};

/* 栈的创建 */
Stack CreateStack(int Max)
{
    Stack S;
    S = malloc(sizeof(struct Mystack));
    if (S == NULL)
        printf("Create stack error!\n");

    S->Array = malloc(sizeof(char) * Max);
    if (S->Array == NULL)
        printf("Create stack error!\n");

    S->Capacity = Max;
    S->Top_of_stack = 0;
    return S;
}

/* 释放栈 */
void DisposeStack(Stack S)
{
    if (S != NULL)
    {   
        free(S->Array);
        free(S);
    }   
}

/* 判断一个栈是否是空栈 */
int IsEmpty(Stack S)
{
    return !S->Top_of_stack;
}

/* 判断一个栈是否满栈 */
int IsFull(Stack S)
{
    if (S->Top_of_stack == S->Capacity - 1)
        return 1;
    else
        return 0;
}

/* 数据入栈 */
int Push(int x, Stack S)
{
    if (IsFull(S))
        printf("The Stack is full!\n");
    else
        S->Array[S->Top_of_stack++] = x;
}

/* 数据出栈 */
int Pop(Stack S)
{
    if (IsEmpty(S))
        printf("The Stack is empty!\n");
    else
        S->Top_of_stack--;
}

/* 将栈顶返回 */
int Top(Stack S)
{
    if (!IsEmpty(S))
        return S->Array[S->Top_of_stack-1];
    printf("The Stack is empty!\n");
    return 0;
}

int main()
{
    int i, len, result;
    char str[100];
    printf("Please input the postfix that you want to compute: \n");
    scanf("%s", str);
    len = strlen(str);
    /* 根据序列的长度来创建栈 */
    struct Mystack *my_stack = CreateStack(len+1);
    for (i = 0; i < len; i++)
    {
        if (str[i] >= '0' && str[i] <= '9')
            Push((int)str[i]-48, my_stack);
        else if (str[i] == '+')
        {
            int x = Top(my_stack);
            Pop(my_stack);
            int y =Top(my_stack);
            Pop(my_stack);
            Push(x+y, my_stack);
            //printf("%d\n", Top(my_stack));
        }
        else if (str[i] == '-')
        {
            int x = Top(my_stack);
            Pop(my_stack);
            int y = Top(my_stack);
            Pop(my_stack);
            Push(x-y, my_stack);
            //printf("%d\n", Top(my_stack));
        }

        else if (str[i] == '*')
        {
            int x = Top(my_stack);
            Pop(my_stack);
            int y = Top(my_stack);
            Pop(my_stack);
            Push(x*y, my_stack);
            //printf("%d\n", Top(my_stack));
        }
        else if (str[i] == '/')
        {
            int x = Top(my_stack);
            Pop(my_stack);
            int y = Top(my_stack);
            Pop(my_stack);
            Push(x/y, my_stack);
            //printf("%d\n", Top(my_stack));
        }
    }
    printf("The result is: %d\n", Top(my_stack));
    Pop(my_stack);
    /* A bug */
//  DisposeStack(my_stack);

    return 0;

}

标签:逆波兰式,堆栈,C语言

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. 博主 发表 2013-10-06 00:00:00 C语言中的堆栈小议
  2. 博主 发表 2014-09-01 16:00:00 C/C++中手动获取调用堆栈
  3. Treri 发表 2013-10-05 16:00:00 C语言中的堆栈小议
  4. 博主 发表 2013-10-06 07:00:00 C语言中的堆栈小议
  5. 老王 发表 2011-11-12 14:17:56 Linux运维利器之ClusterShell
  6. soffee 发表 2013-03-08 01:00:06 惊喜礼物“月月”有,Le Parcel邮寄贴心呵护
  7. Timothy 发表 2012-09-24 16:37:00 Filco 圣手一代青轴入手记
  8. abcd9.com 发表 2013-02-27 02:45:08 PHP将数据库导出为excel表
  9. lovebite 发表 2012-12-18 09:27:21 为什么键盘是QWERT,而不是ABCDE?
  10. Yuku 发表 2013-03-16 08:14:00 Big Cry
  11. Jordan Golson 发表 2013-03-18 21:08:46 Samsung Galaxy S 4 Benchmarks Nearly Twice as Fast
  12. Jordan Golson 发表 2013-03-20 22:09:26 Pixelmator Crashing Issue Fixed in OS X 10.8.3 [Ma

发表评论