注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

堆栈计算逆波兰记法使用C语言实现

OC/C/C++ 水墨上仙 3263次浏览 已收录 手机上查看

堆栈计算逆波兰式使用C语言实现
逆波兰式(Reverse Polish notation,RPN,或逆波兰记法),也叫后缀表达式(将运算符写在操作数之后)
一个表达式E的后缀形式可以如下定义:
(1)如果E是一个变量或常量,则E的后缀式是E本身。
(2)如果E是E1 op E2形式的表达式,这里op是如何二元操作符,则E的后缀式为E1’E2′ op,这里E1’和E2’分别为E1和E2的后缀式。
(3)如果E是(E1)形式的表达式,则E1的后缀式就是E的后缀式。
如:我们平时写a+b,这是中缀表达式,写成后缀表达式就是:ab+
(a+b)c-(a+b)/e的后缀表达式为:
(a+b)
c-(a+b)/e
→((a+b)c)((a+b)/e)-
→((a+b)c
)((a+b)e/)-
→(ab+c)(ab+e/)-
→ab+c
ab+e/-

#include 
#include 
#include 

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语言实现
喜欢 (2)
[开心洋葱]
分享 (0)
水墨上仙
关于作者:
水墨上仙
……
加载中……