QQ登录

只需一步，快速开始

 找回密码
 注册

QQ登录

只需一步，快速开始

返回列表 发新帖
查看: 3932|回复: 2

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

[复制链接]
发表于 2012-4-1 19:45:47 | 显示全部楼层 |阅读模式
#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[MAX_SIZE];
    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[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 == -1)
    {
        return FAILED;
    }
    else
    {
        *data = stack->data[stack->top];
        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);
}
回复

使用道具 举报

 楼主| 发表于 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[MAX_SIZE];
    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[1]);
    }
    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[stack->top];
        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;
}
回复

使用道具 举报

 楼主| 发表于 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[MAX_STACK_DEPTH];
    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[stack->top];
        return SUCCESS;
    }
}

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

    len = strlen(str);
    p = str;
    while(len > 0)
    {
                num += ((int)*p++ - 4 * 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[MAX_NUMBER_LEN] = {'\0'};
    int i = 0;
    int paren = 0;
    p = str;

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

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

        if(num[0] != '\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;
}
回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则

GMT+8, 2024-4-25 02:33 , Processed in 0.200168 second(s), 15 queries .

© 2021 Powered by Discuz! X3.5.

快速回复 返回顶部 返回列表