网站 › 『 编程之美 』 › C语言结业作业--计算器(用栈写)

wai1216 发表于 2016-8-30 17:12:33

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

本帖最后由 wai1216 于 2016-9-12 18:41 编辑

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

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

第一个：node.h

#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


#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


#include "node.h"

typedef struct
{
      Stack * sp;
}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




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

int SignTab =
{
    /*   +   -   *   /   ()#   */
/*+*/         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 = InitStack(100);
      if(cp->sp == 0)
                return 0;
      cp->sp = InitStack(100);
      if(cp->sp == 0)
      {
                free(cp->sp);
                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;
}

int _Orcal(Stack * sp,int * k,ElementType * pdata)
{
      return SignTab == 1;
}

int _Or0(Stack * sp,int * k,ElementType * pdata)
{
      return SignTab == 0;
}

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

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

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

int R_Free(Cal * cp)
{
      free(cp->sp);
      free(cp->sp);
      free(cp);
}

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


运行文件:1.c

#include "cal.h"
#define MAX 50

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

      IsStack2(cp,cal,&a);
}

查看完整版本: C语言结业作业--计算器(用栈写)