C语言结业作业--计算器(用栈写)

wai1216

暑假蛮充数的，但是电脑不常打开，开学啦。这个结业作业断断续续写了很久，从放假到开学。
说下思路。分成两个栈，一个栈存放数字，一个栈存放运算符。
开始一直没想通怎么实现判断优先级，一味的将数据压入两个栈，然后一步一步的判断优先级，几番修改始终某些例子得不到应有的答案。
今天才想明白，原来是看一个运算符和它之后下一个运算符是否满足优先级。如果满足优先级，进行运算，不满足压入栈。
关键在于判断即将入栈的运算符(此时还未入栈)和栈顶的运算符事是否满足优先级。上代码

只写了整数的计算，还未考虑减法之后出现负数的情况。可能有些地方还不完美哈~

第一个：node.h

[C] 纯文本查看 复制代码

#define NULL 0
#define ElementType char


typedef struct
{
        ElementType * pbuffer;
        int * number;
        int max;
        int top;
        int i_top;
}Stack;

Stack * InitStack(int n);

int Push(Stack * sp,ElementType pdata);

int Push_i(Stack * sp,ElementType pdata);

int _DelSign(Stack * sp, ElementType data, int n);

int _InsADel(Stack * sp,int data,int k);

int IsEmpty(Stack * sp);

int IsFull(Stack * sp);

对应的:node.c

[C] 纯文本查看 复制代码

#include "node.h"


Stack * InitStack(int n)
{
        Stack * sp = NULL;
        sp = (Stack *)malloc(sizeof(Stack));
        if(!sp)
                return 0;
        sp->pbuffer = NULL;
        sp->pbuffer = (ElementType *)malloc(sizeof(ElementType));
        if(!sp->pbuffer)
                return 0;
        sp->number = NULL;
        sp->number = (int *)malloc(sizeof(int));
        if(!sp->number)
                return 0;
        sp->max = n;
        sp->top = -1;
        sp->i_top = -1;
        return sp;
}

int Push(Stack * sp,ElementType pdata)
{
        if(IsFull(sp))
                return 0;
        sp->top++;
        memcpy(sp->pbuffer + sp->top,&pdata,sizeof(ElementType));
}

int Push_i(Stack * sp,ElementType pdata)
{
        sp->i_top++;
        memcpy(sp->number + sp->i_top,&pdata,sizeof(int));
}


int _DelSign(Stack * sp, ElementType data, int n) /* 栈2 char */
{
        int i = 0;
        if(IsEmpty(sp))
                return 0;
        memcpy( &data, sp->pbuffer + n, sizeof(ElementType)); 
        for( i = n + 1; i <= sp->top ; i++)
        {
                memcpy(sp->pbuffer + i, sp->pbuffer + i + 1,sizeof(ElementType));
        }
        sp->top--;
}

int _InsADel(Stack * sp,int data,int k)  /* 栈1 int */
{
        int i = 0;
        memcpy(sp->number + k, &data, sizeof(int));
        for( i = k + 1; i <= sp->i_top ; i++)
        {
                memcpy(sp->number + i, sp->number + i + 1,sizeof(int));
        }
        sp->i_top--;
}

int IsEmpty(Stack * sp)
{
        return sp->top == -1;
}

int IsFull(Stack * sp)
{
        return sp->top == sp->max;
}

第二个: cal.h

[C] 纯文本查看 复制代码

#include "node.h"

typedef struct
{
        Stack * sp[2];
}Cal;

Cal * InitCal();
/*数据的分栈*/
int IsStack2(Cal * cp,ElementType * cal,int * k);

int R_Atoi(ElementType * pdata);

int R_IsStack(ElementType * pdata);

int R_Num(ElementType * pdata);

/*数据的处理*/

int _SignTab(Stack * sp,int * k);

int _Orcal(Stack * sp,int * k,ElementType * pdata);

int _Or0(Stack * sp,int * k,ElementType * pdata);

int _Operator(Stack * sp,int * k);

int _Restcal(Cal * cp,int *k, ElementType * cal);

int Start_cal(int n,Stack * sp,int k);
int R_Free(Cal * cp);

int _cal(Cal * cp,int * k);

对应的cal.c

[C] 纯文本查看 复制代码

#include "cal.h"
#include <stdio.h>

int SignTab[7][7] = 
{
    /*   +   -   *   /   (  )  #     */
/*+*/         1,  1, -1, -1, -2, 1, 1,
/*-*/         1,  1, -1, -1, -2, 1, 1,
/***/         1,  1,  1,  1, -2, 1, 1,
/*/*/        -1, -1,  1,  1, -2, 1, 1, 
/*(*/   -1, -1, -1, -1, -2, 0, -9,
/*)*/        -1, -1, -1, -1, -9,-9, -9,
/*#*/        -1, -1, -1, -1, -9,-9, 0,
};

char * str = "+-*/()#";
char * str_i = "0123456789";

Cal * InitCal()
{
        Cal * cp = NULL;
        cp = (Cal *)malloc(sizeof(Cal));
        if(!cp)
                return 0;
        cp->sp[0] = InitStack(100);
        if(cp->sp[0] == 0)
                return 0;
        cp->sp[1] = InitStack(100);
        if(cp->sp[1] == 0)
        {
                free(cp->sp[0]);
                free(cp);
                return 0;
        }
        return cp;
}

int R_Atoi(ElementType * pdata)
{
        int i = 0;
        for(i = 0; i < strlen(str_i); i++)
        {
                if(*pdata == *(str_i + i))
                {
                        return 1;
                }
        }
        return 0;
}


int Start_cal(int n,Stack * sp,int k)
{
        int a = 0;
        k--;
        switch(n)
        {
                case 0:a = *(sp->number + k) + *(sp->number + k + 1) ; break;
                case 1:a = *(sp->number + k) - *(sp->number + k + 1) ; break;
                case 2:a = *(sp->number + k) * *(sp->number + k + 1) ; break;
                case 3:a = *(sp->number + k) / *(sp->number + k + 1) ; break;
        }
        return a;
}


int R_IsStack(ElementType * pdata)
{
        int i = 0;
        for(i = 0; i < strlen(str); i++)
        {
                if(*pdata == *(str + i))
                {
                        return 1;
                }
        }
        return 0;
}

int R_Num(ElementType * pdata)
{
        int i = 0;
        for(i = 0; i < strlen(str); i++)
        {
                if(*pdata == *(str + i)) 
                {
                        return i;
                }
        }
        return 10;
}

int _SignTab(Stack * sp,int * k)
{
        return SignTab[R_Num(sp->pbuffer + (*k))][R_Num(sp->pbuffer + (*k) + 1)];
}

int _Orcal(Stack * sp,int * k,ElementType * pdata)
{
        return SignTab[R_Num(sp->pbuffer + (*k))][R_Num(pdata)] == 1;
}

int _Or0(Stack * sp,int * k,ElementType * pdata)
{
        return SignTab[R_Num(sp->pbuffer + (*k))][R_Num(pdata)] == 0;
}

int _Operator(Stack * sp,int * k)
{
        return R_Num((sp->pbuffer + (*k)));
}

int IsStack2(Cal * cp,ElementType * cal,int * k)
{
        char num[100], i = 0;
        Push(cp->sp[1],'#');
        
        while( R_Atoi(cal) || R_IsStack(cal))
        {
                if(R_Atoi(cal))
                {
                        while(R_Atoi(cal))
                        {
                                *(num + i) = *cal;
                                i++;
                                *cal++;
                        }
                        Push_i(cp->sp[0],atoi(num));
                        i = 0;
                        memset(num,0,sizeof(num));
                }
                else if(R_IsStack(cal))
                {
                        if(_Orcal(cp->sp[1], k,cal)) 
                        {
                                if(*(cp->sp[1]->pbuffer + (*k) - 1) == '(')
                                {
                                        i = Start_cal(R_Num(cp->sp[1]->pbuffer + (*k)),cp->sp[0], (*k)-1);                                
                                        _InsADel(cp->sp[0], i, *k - 1 - 1);
                                        _DelSign(cp->sp[1], *cal, *k - 1);
                                }
                                else if(_Or0(cp->sp[1], k, (cp->sp[1]->pbuffer + (*k) + 1)))
                                {
                                        _DelSign(cp->sp[1], *cal, *k - 1);
                                        _DelSign(cp->sp[1], *cal, *k - 1);
                                }
                                else
                                {
                                        _cal(cp,k);
                                }
                        }
                        else
                        {
                                (*k)++;
                        }
                        Push(cp->sp[1],*cal);
                        i = 0;
                        *cal++;
                }
        }
        (*k) = 0;
        _Restcal(cp, k, cal);
        
}

int _Restcal(Cal * cp,int *k, ElementType * cal)
{
        int i = 0;
        while( cp->sp[1]->top >= 1)
        {
                if(_Orcal(cp->sp[1], k, (cp->sp[1]->pbuffer + (*k) + 1)))
                {
                        _cal(cp,k);
                        (*k) = 0;
                }
                else if(_Or0(cp->sp[1], k, (cp->sp[1]->pbuffer + (*k) + 1)))
                {
                        _DelSign(cp->sp[1], *cal, *k - 1);
                        _DelSign(cp->sp[1], *cal, *k - 1);
                        (*k) = 0;
                }
                else
                {
                        if(*cal != '(')
                        {
                                (*k)++;
                        }
                }        
        }
        
        (*k) = 0;
        
        printf("  =%d ",*(cp->sp[0]->number));
        _InsADel(cp->sp[0], i, *k);
        R_Free(cp);
}

int R_Free(Cal * cp)
{
        free(cp->sp[1]);
        free(cp->sp[0]);
        free(cp);
}

int _cal(Cal * cp,int * k)
{
        int i = 0;
        i = Start_cal(R_Num(cp->sp[1]->pbuffer + (*k)),cp->sp[0], *k);
        _InsADel(cp->sp[0], i, *k - 1);
        _DelSign(cp->sp[1], *(cp->sp[1]->pbuffer + (*k)), *k - 1); 
}

运行文件:1.c

[C] 纯文本查看 复制代码

#include "cal.h"
#define MAX 50

void main()
{
        char cal[MAX];
        int a = 0;
        Cal * cp = InitCal();
        if(!cp)
                return ;
        scanf("%49s",cal);
        *(cal + strlen(cal)) = '#';
        

        IsStack2(cp,cal,&a);
}