voodoomaster 发表于 2012-4-1 19:45:47

贴个C语言四则运算小程序，双栈实现的，供研究

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 64
#define MAX_LEN 128
#define SUCCESS 0
#define FAILED 1
#define FULL 2
#define EMPTY 3
#define OVERFLOW -1
#define UNDERFLOW -2

typedef union
{
    int num;
    char op;
}ELEMENT;

typedef struct
{
    ELEMENT data;
    int top = -1;
}STACK;

STACK NumStack, OpStack;

int InitStack(STACK *stack);
int JudgeStack(STACK *stack);
int PopStack(STACK *stack, ELEMENT *data);
int PushStack(STACK *stack, ELEMENT *data);
int GetStackTop(STACK *stack, ELEMENT *data);

int GetCharType(char inputchar);
int GetOpLv(char inputchar);
int Expr(char *str);
int CharToNum(char inputchar);
char NumToChar(int inputnum);
int StrToNum(char *inputstr);
char *NumToStr(int inputnum);
void ReverseStr(char *str);
int Calc(int num1, int num2, char op);
int RemoveSpace(char *inputstr, char *outputstr);

void main(void)
{
    char *str = "#1+ ( 3-2)*5 + 4#";
    char *calcstr;
    int result;

    calcstr = (char *)malloc(MAX_LEN * sizeof(char));
    memset(calcstr, 0, MAX_LEN * sizeof(char));

    RemoveSpace(str, calcstr);

    result = Expr(calcstr)
    printf("the calc result is: %d\n", result);
}

int InitStack(STACK *stack)
{
    stack->top = -1;
    return SUCCESS;
}

int JudgeStack(STACK *stack)
{
    if(stack->top == -1)
    {
      return EMPTY;
    }
    else if(stack->top == MAX_SIZE - 1)
    {
      return FULL;
    }
}

int PushStack(STACK *stack, ELEMENT *data)
{
    if(stack->top == MAX_SIZE - 1)
    {
      return OVERFLOW;
    }
    else
    {
      stack->data = *data;
      return SUCCESS;
    }
}

int PopStack(STACK *stack, ELEMENT *data)
{
    if(stack->top == -1)
    {
      return UNDERFLOW;
    }
    else
    {
      *data = stack->data;
      return SUCCESS;
    }
}

int GetStackTop(STACK *stack, ELEMENT *data)
{
    if(stack->top == -1)
    {
      return FAILED;
    }
    else
    {
      *data = stack->data;
      return SUCCESS;
    }
}

int GetOpLv(char inputchar)
{
    if(inputchar == '#')
    {
      return 0;
    }
    else if(inputchar == '+' || inputchar == '-')
    {
      return 1;
    }
    else if(inputchar == '*' || inputchar == '/')
    {
      return 2;
    }
}

int GetCharType(char inputchar)
{
    if(isdigit(inputchar))
    {
      return 1;
    }

    if(inputchar == '+' || inputchar == '-' || inputchar == '*' || inputchar == '/')
    {
      return 2;
    }

    if(inputchar == '(')
    {
      return 3;
    }

    if(inputchar == ')')
    {
      return 4;
    }
}

int CharToNum(char inputchar)
{
    int num;
    num = (int)inputchar - 48;
    return num;
}

char NumToChar(int inputnum)
{
    char chr;
    chr = (char)inputnum + 48;
    return chr;
}

void ReverseStr(char *str)
{
    char temp;
    int len;
    int i;

    len = strlen(str);
    for(i = 0; i <= (int)len/2 - 1; i++)
    {
      temp = *(str + i);
      *(str + i) = *(str + len - 1 - i);
      *(str + len - 1 - i) = temp;
    }
}

int StrToNum(char *inputstr)
{
    int len;
    int num = 0;
    char *p;

    len = strlen(inputstr);
    p = inputstr;
    while(len > 0)
    {
                num += CharToNum(*p++) * pow(10, --len);
    }
    return num;
}

char *NumToStr(int inputnum)
{
    char *str;
    char *p;
    int num = inputnum;

    str = (char *)malloc(MAX_EXPRESSION_LEN * sizeof(char));
        memset(str, 0, MAX_EXPRESSION_LEN);
    p = str;

    while(num > 0)
    {
      *p = NumToChar(num % 10);
      num = (num - (num % 10)) / 10;
      p++;
    }
    ReverseStr(str);
    return str;
}

int Calc(int num1, int num2, char op)
{
    switch (op)
    {
      case '+':
            return (num1 + num2);
      case '-':
            return (num1 - num2);
      case '*':
            return (num1 * num2);
      case '/':
            return (num1 / num2);
    }
}

int RemoveSpace(char *inputstr, char *outputstr)
{
    char *p1;
    char *p2;
    p1 = inputstr;
    p2 = outputstr;

    while(*p1 != '\0')
    {
      if(isspace(*p1))
      {
            p1++;
            continue;
      }
      else
      {
            *p2++ = *p1++;
      }
    }
    *p2 = '\0';

    return SUCCESS;
}

int Expr(char *str)
{
    char *p;

    p = str;
    InitStack(NumStack);
    InitStack(OpStack);
    while (*p != ’#’ || GetTop(OpStack) != ’#’)
    {
      if (isdigit(*p))
      {
            PushStack(NumStack, p++);
      }
      else
      {
            if(*p == '(')
            {
                PushStack(OpStack, *p);
            }
            else if(*p == ')')
            {
            }
            else
            {
            }
      }
    }
    return GetTop(OPND);
}
{
            r = ComparePriority(GetTop(OPTR), c);
            switch(r)
            {
                case '<':
                  Push(OPTR, c);
                  c = getchar();
                  break;
                case '=':
                  Pop(OPTR, x);
                  c = getchar();
                  break;
                case '>':
                  Pop(OPTR, op);
                  Pop(OPND, b);
                  Pop(OPND, a);
                  value = Operate(a, op, b);
                  Push(OPND, value);
                  break;
            }
    return GetTop(OPND);
}

voodoomaster 发表于 2012-4-5 20:15:41

又忙了半天，终于写好了，现在这个程序可以实现四则运算，不过数字都是个位数，后面看看能不能改成支持多位数的

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 64
#define MAX_LEN 128
#define SUCCESS 0
#define FAILED 1
#define FULL 2
#define EMPTY 3
#define OVERFLOW -1
#define UNDERFLOW -2

typedef union
{
    int num;
    char op;
}ELEMENT;

typedef struct
{
    ELEMENT data;
    int top;
}STACK;

STACK *NumStack, *OpStack;

int InitStack(STACK *stack);
int JudgeStack(STACK *stack);
int PopStack(STACK *stack, ELEMENT *data);
int PushStack(STACK *stack, ELEMENT *data);
int GetStackTop(STACK *stack, ELEMENT *data);

int Expr(char *str);
void CalcPlainExpr(void);
int CharToNum(char inputchar);
char NumToChar(int inputnum);
int StrToNum(char *inputstr);
char *NumToStr(int inputnum);
void ReverseStr(char *str);
int CalcNum(int num1, int num2, char op);

int main(int argc, char *argv[])
{
    //char *s = "1+ ( 3-2)*5 + 4#";
    //char *s = "1+ 3-2*5#";
    //char *s = "1+ 3-2 + 4#";
    //char *s;
    int result;
    ELEMENT first;

    //s = (char *)malloc(MAX_LEN * sizeof(char));
    //memset(s, 0, MAX_LEN * sizeof(char));

    NumStack = (STACK *)malloc(sizeof(STACK));
    OpStack = (STACK *)malloc(sizeof(STACK));
    first.op = '#';

    //printf("please input the expression:\n");
    //gets(s);
    InitStack(NumStack);
    InitStack(OpStack);
    PushStack(OpStack, &first);

    if(argc != 2)
    {
      printf("wrong input!");
      return 0;
    }
    else
    {
      result = Expr(argv);
    }
    printf("the calc result is: %d\n", result);
    return 1;
}

int InitStack(STACK *stack)
{
    stack->top = -1;
    return SUCCESS;
}

int JudgeStack(STACK *stack)
{
    if(stack->top == -1)
    {
      return EMPTY;
    }
    else if(stack->top == MAX_SIZE - 1)
    {
      return FULL;
    }
}

int PushStack(STACK *stack, ELEMENT *data)
{
    if(stack->top == MAX_SIZE - 1)
    {
      return OVERFLOW;
    }
    else
    {
      stack->data[++(stack->top)] = *data;
      return SUCCESS;
    }
}

int PopStack(STACK *stack, ELEMENT *data)
{
    if(stack->top == -1)
    {
      return UNDERFLOW;
    }
    else
    {
      *data = stack->data[(stack->top)--];
      return SUCCESS;
    }
}

int GetStackTop(STACK *stack, ELEMENT *data)
{
    if(stack->top < 0 || stack->top > MAX_SIZE - 1)
    {
      return FAILED;
    }
    else
    {
      *data = stack->data;
      return SUCCESS;
    }
}

int CharToNum(char inputchar)
{
    int num;
    num = (int)inputchar - 48;
    return num;
}

char NumToChar(int inputnum)
{
    char chr;
    chr = (char)inputnum + 48;
    return chr;
}

void ReverseStr(char *str)
{
    char temp;
    int len;
    int i;

    len = strlen(str);
    for(i = 0; i <= (int)len/2 - 1; i++)
    {
      temp = *(str + i);
      *(str + i) = *(str + len - 1 - i);
      *(str + len - 1 - i) = temp;
    }
}

int StrToNum(char *inputstr)
{
    int len;
    int num = 0;
    char *p;

    len = strlen(inputstr);
    p = inputstr;
    while(len > 0)
    {
                num += CharToNum(*p++) * pow(10, --len);
    }
    return num;
}

char *NumToStr(int inputnum)
{
    char *str;
    char *p;
    int num = inputnum;

    str = (char *)malloc(MAX_LEN * sizeof(char));
        memset(str, 0, MAX_LEN);
    p = str;

    while(num > 0)
    {
      *p = NumToChar(num % 10);
      num = (num - (num % 10)) / 10;
      p++;
    }
    ReverseStr(str);
    return str;
}

int CalcNum(int num1, int num2, char op)
{
    int result;
    switch (op)
    {
      case '+':
            result = num2 + num1;
            break;
      case '-':
            result = num2 - num1;
            break;
      case '*':
            result = num2 * num1;
            break;
      case '/':
            result = num2 / num1;
            break;
    }
    return result;
}

void CalcPlainExpr(void)
{
    ELEMENT num1;
    ELEMENT num2;
    ELEMENT op;
    ELEMENT top;
    ELEMENT temp;

    while(1)
    {
      if(GetStackTop(OpStack, &top) == FAILED)
      {
            break;
      }
      else if(top.op == '(')
      {
            PopStack(OpStack, &temp);
            break;
      }
      else
      {
            PopStack(NumStack, &num1);
            PopStack(NumStack, &num2);
            PopStack(OpStack, &op);
            temp.num = CalcNum(num1.num, num2.num, op.op);
            PushStack(NumStack, &temp);
      }
    }
}

int Expr(char *str)
{
    char *p;
    ELEMENT top;
    ELEMENT result;
    ELEMENT num1;
    ELEMENT num2;
    ELEMENT op;
    ELEMENT temp;

    p = str;

    while (1)
    {
      if(*p == '\0')
      {
            CalcPlainExpr();
            break;
      }
      else if(isspace(*p))
      {
            p++;
      }
      else if (isdigit(*p))
      {
            temp.num = CharToNum(*p++);
            PushStack(NumStack, &temp);
      }
      else if(*p == '(')
      {
            temp.op = *p++;
            PushStack(OpStack, &temp);
      }
      else if(*p == ')')
      {
            CalcPlainExpr();
            p++;
      }
      else if(*p == '+' || *p == '-')
      {
            if(GetStackTop(OpStack, &top) == FAILED)
            {
                temp.op = *p++;
                PushStack(OpStack, &temp);
            }
            else if(top.op == '+' || top.op == '-' || top.op == '*' || top.op == '/')
            {
                PopStack(NumStack, &num1);
                PopStack(NumStack, &num2);
                PopStack(OpStack, &op);
                temp.num = CalcNum(num1.num, num2.num, op.op);
                PushStack(NumStack, &temp);
            }
            else
            {
                temp.op = *p++;
                PushStack(OpStack, &temp);
            }
      }
      else if(*p == '*' || *p == '/')
      {
            if(GetStackTop(OpStack, &top) == FAILED)
            {
                temp.op = *p++;
                PushStack(OpStack, &temp);
            }
            else if(top.op == '*' || top.op == '/')
            {
                PopStack(NumStack, &num1);
                PopStack(NumStack, &num2);
                PopStack(OpStack, &op);
                temp.num = CalcNum(num1.num, num2.num, op.op);
                PushStack(NumStack, &temp);
            }
            else
            {
                temp.op = *p++;
                PushStack(OpStack, &temp);
            }
      }
      else
      {
            printf("error!\n");
            break;
      }
    }

    GetStackTop(NumStack, &result);
    return result.num;
}

voodoomaster 发表于 2012-4-9 09:35:41

加入多位数判断功能，并且优化了各个函数，目前代码已经比较完美了

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define MAX_STACK_DEPTH 64
#define MAX_NUMBER_LEN 128
#define SUCCESS 1
#define FAILED 0

typedef union
{
    int num;
    char op;
}ELEMENT;

typedef struct
{
    ELEMENT data;
    int top;
}STACK;

STACK *NumStack, *OpStack;

void InitStack(STACK *stack);
int PopStack(STACK *stack, ELEMENT *data);
int PushStack(STACK *stack, ELEMENT *data);
int GetStackTop(STACK *stack, ELEMENT *data);
int Expr(char *str, ELEMENT *data);
int CalcChain(void);
int CalcOnce(void);
int StrToNum(char *str);

int main(int argc, char *argv[])
{
    ELEMENT result;

    NumStack = (STACK *)malloc(sizeof(STACK));
    OpStack = (STACK *)malloc(sizeof(STACK));
    InitStack(NumStack);
    InitStack(OpStack);

    char *s;
    s = (char *)malloc(MAX_NUMBER_LEN * sizeof(char));
    memset(s, 0, MAX_NUMBER_LEN * sizeof(char));
   
    printf("please input the expression:\n");
    gets(s);

    if(Expr(s, &result) == FAILED)
    {
      return FAILED;
    }

    printf("the calc result is: %d\n", result.num);
    free(NumStack);
    free(OpStack);
    return SUCCESS;
}

void InitStack(STACK *stack)
{
    stack->top = -1;
}

int PushStack(STACK *stack, ELEMENT *data)
{
    if(stack->top == MAX_STACK_DEPTH - 1)
    {
      return FAILED;
    }
    else
    {
      stack->data[++(stack->top)] = *data;
      return SUCCESS;
    }
}

int PopStack(STACK *stack, ELEMENT *data)
{
    if(stack->top == -1)
    {
      return FAILED;
    }
    else
    {
      *data = stack->data[(stack->top)--];
      return SUCCESS;
    }
}

int GetStackTop(STACK *stack, ELEMENT *data)
{
    if(stack->top < 0 || stack->top > MAX_STACK_DEPTH - 1)
    {
      return FAILED;
    }
    else
    {
      *data = stack->data;
      return SUCCESS;
    }
}

int StrToNum(char *str)
{
    int len;
    int num = 0;
    char *p;

    len = strlen(str);
    p = str;
    while(len > 0)
    {
                num += ((int)*p++ - 48) * pow(10, --len);
    }
    return num;
}

int CalcOnce(void)
{
    ELEMENT num1;
    ELEMENT num2;
    ELEMENT op;
    ELEMENT temp;

    if(PopStack(NumStack, &num1) == FAILED)
    {
      return FAILED;
    }
    if(PopStack(NumStack, &num2) == FAILED)
    {
      return FAILED;
    }
    if(PopStack(OpStack, &op) == FAILED)
    {
      return FAILED;
    }

    switch (op.op)
    {
      case '+':
            temp.num = num2.num + num1.num;
            break;
      case '-':
            temp.num = num2.num - num1.num;
            break;
      case '*':
            temp.num = num2.num * num1.num;
            break;
      case '/':
            if(num1.num == 0)
            {
                return FAILED;
            }
            else
            {
                temp.num = num2.num / num1.num;
            }
            break;
    }

    if(PushStack(NumStack, &temp) == FAILED)
    {
      return FAILED;
    }
    else
    {
      return SUCCESS;
    }
}

int CalcChain(void)
{
    ELEMENT num1;
    ELEMENT num2;
    ELEMENT op;
    ELEMENT top;
    ELEMENT temp;

    while(1)
    {
      if(GetStackTop(OpStack, &top) == FAILED)
      {
            break;
      }
      else if(top.op == '(')
      {
            PopStack(OpStack, &temp);
            break;
      }
      else
      {
            if(CalcOnce() == FAILED)
            {
                return FAILED;
            }
      }
    }

    return SUCCESS;
}

int Expr(char *str, ELEMENT *data)
{
    ELEMENT top;
    ELEMENT result;
    ELEMENT num1;
    ELEMENT num2;
    ELEMENT op;
    ELEMENT temp;
    char *p;
    char num = {'\0'};
    int i = 0;
    int paren = 0;
    p = str;

    while (1)
    {
      if(isspace(*p))
      {
            p++;
            continue;
      }

      if(isdigit(*p))
      {
            num = *p++;
            continue;
      }

      if(num != '\0')
      {
            temp.num = StrToNum(num);
            if(PushStack(NumStack, &temp) == FAILED)
            {
                return FAILED;
            }
            memset(num, 0, MAX_NUMBER_LEN * sizeof(char));
            i = 0;
      }

      if(*p == '\0')
      {
            if(CalcChain() == FAILED)
            {
                return FAILED;
            }
            else
            {
                break;
            }
      }

      if(*p == '(')
      {
            paren++;
            temp.op = *p++;
            if(PushStack(OpStack, &temp) == FAILED)
            {
                return FAILED;
            }
            continue;
      }

      if(*p == ')')
      {
            paren--;
            if(CalcChain() == FAILED)
            {
                return FAILED;
            }
            else
            {
                p++;
            }
            continue;
      }

      if(*p == '+' || *p == '-')
      {
            if(GetStackTop(OpStack, &top) == FAILED)
            {
                temp.op = *p++;
                if(PushStack(OpStack, &temp) == FAILED)
                {
                  return FAILED;
                }
            }
            else if(top.op == '+' || top.op == '-' || top.op == '*' || top.op == '/')
            {
                if(CalcOnce() == FAILED)
                {
                  return FAILED;
                }
            }
            else
            {
                temp.op = *p++;
                if(PushStack(OpStack, &temp) == FAILED)
                {
                  return FAILED;
                }
            }
            continue;
      }

      if(*p == '*' || *p == '/')
      {
            if(GetStackTop(OpStack, &top) == FAILED)
            {
                temp.op = *p++;
                if(PushStack(OpStack, &temp) == FAILED)
                {
                  return FAILED;
                }
            }
            else if(top.op == '*' || top.op == '/')
            {
                if(CalcOnce() == FAILED)
                {
                  return FAILED;
                }
            }
            else
            {
                temp.op = *p++;
                if(PushStack(OpStack, &temp) == FAILED)
                {
                  return FAILED;
                }
            }
            continue;
      }

      return FAILED;
    }

    if(paren != 0)
    {
      printf("input paren not match!\n");
      return FAILED;
    }

    if(GetStackTop(NumStack, data) == FAILED)
    {
      return FAILED;
    }

    return SUCCESS;
}
页: [1]
查看完整版本: 贴个C语言四则运算小程序，双栈实现的，供研究