表达式求值-C语言实现

C/C++ 2015年12月17日

表达式求值问题,是一个经典的问题。但是要考虑运算符的优先级以及括号的问题,对于毫无经验的"新手"来讲,也会是个难题。枫竹梦今天介绍一种求值的方法。

基本概念

常见的表达式形式称之为中缀表达式。如:

1 + 2 * 3 * (4 + 5)

之所以称为中缀表达式,对于有两个操作数的运算符,将运算符写在中间。

而对表达式最简单的求解方式就是将其转换为后缀表达式。如上面的中缀表达式转化为后缀表达式即为:

1 2 3 * 4 5 + * +

运算数的相对位置没有改变,而运算符的位置改变了,而且后缀表达式中不再需要括号,表达式的值就按运算符出现的顺序进行计算就好。计算的过程大致描述如下:

从左向右,遇到运算数,保存。遇到运算符,则取出最后保存运算数进行计算,并将结果保存。直到表达式结束。

NB:取出运算数的个数取决于运算符需要的运算数的个数。

对于上面的表达式:

  1. 依次保存1, 2, 3;
  2. 遇到*,取出2和3计算,并将结果6保存,此时保存数为1, 6;
  3. 继续保存4和5,此时保存数为1, 6, 4, 5;
  4. 遇到+,取出4和5计算,并将结果9保存,此时保存数为1, 6, 9;
  5. 遇到*,取出6和9计算,并将结果54保存,此时保存数为1, 54;
  6. 遇到+,取出1和54计算,并将结果55保存,此时保存数为55;
  7. 后缀表达式扫描完毕,此时保存的数55即为计算结果。

求值的过程还是比较简单的,而这里最关键的问题是如果将中缀表达式转化为中缀表达式。

C语言实现

中缀表达式转化为中缀表达式?答案就是利用堆栈这种后进先出的数据结构来实现。具体如何实现就留给大家进行思考实现了。这下面的实现过程中,利用到了中缀表达式,但是并没对其进行保存,而是一边转化一边进行求值,可以很轻易的将其提炼出来。

求值主要流程在evaluate()函数中,程序使用了两个栈结构,分别保存运算符和运算数。对于运算符的优先级的处理在cmp_opr()函数中。实现中对输入表达的容错性进行了一定的处理,但还不完善。使用的方法如下:

./evaluate 1+2*3*\(4+5\)

NB:在Linux平台需要对括号进行转义,而在Windows平台需要对^进行转义,转义的方法是使用2个^^表示一个^

目前支持的运算符号有+-*/^()

/* 
 * evaluate.c - evaluate an expression
 * Copyright (C) 2013-2015 FURZOOM.COM
 *
 * @file      evaluate.c
 * @brief     evaluate an expression
 * @details   evaluate an expression
 * @author    Yan Ma
 * @version   1.0
 * @date      2015-12
 * @history
 * @website  http://furzoom.com/
 */

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

/* macro */
#define OPR_STACK_SIZE 100
#define OPD_STACK_SIZE 100
#define SIGN_NUM 8

/* constant */
typedef enum STACK_TYPE {OPR, OPD} stack_type;
typedef enum OPERATOR {ADD, SUB, MUL, DIV, POW, L_P, R_P, EOE} Operator;

/* data structure */
typedef struct OPR_STACK {
    int size;
    int capacity;
    char data[OPR_STACK_SIZE];
} opr_stack;

typedef struct OPD_STACK {
    int size;
    int capacity;
    double data[OPD_STACK_SIZE];
} opd_stack;


/* stack */
void *init_stack(stack_type type);
void free_stack(void *s);
int push(void *s, stack_type type, void *e);
void *pop(void *s, stack_type type);
void *top(void *s, stack_type type);
int empty(void *s, stack_type type);
int size(void *s, stack_type type);

double evaluate(char *expr);
double readnum(const char *p, int *pos);
char cmp_opr(char cur, char top);
double cal(double d1, double d2, char op);
char *trim(char *s);

int main(int argc, char *argv[])
{
    char input[OPD_STACK_SIZE * 10];

    if (argc != 2)
    {
        fprintf(stderr, "Usage: %s [expression]\n", argv[0]);
        exit(EXIT_FAILURE);
    }
    strncpy (input, argv[1], OPD_STACK_SIZE * 10 - 1);
    double result = evaluate(input);
    printf("%lf\n", result);

    return 0;
}

void *init_stack(stack_type type)
{
    void *val = NULL;
    switch (type)
    {
        case OPR:
        {
            opr_stack *s = (opr_stack *)malloc(sizeof(opr_stack));
            if (s == NULL)
                break;
            s->size = 0;
            s->capacity = OPR_STACK_SIZE;
            val = s;
            break;
        }
        case OPD:
        {
            opd_stack *s = (opd_stack *)malloc(sizeof(opd_stack));
            if (s == NULL)
                break;
            s->size = 0;
            s->capacity = OPD_STACK_SIZE;
            val = s;
            break;
        }
        default:
            exit(EXIT_FAILURE);
            break;
    }
    return val;
}

void free_stack(void *s)
{
    if (s == NULL)
    {
        return;
    }
    else
    {
        free(s);
    }
}

int push(void *s, stack_type type, void *e)
{
    if (s == NULL)
    {
        return 1;
    }
    else
    {
        switch (type) 
        {
            case OPR:
            {
                opr_stack *ss = (opr_stack *)s;
                char *data = (char *)e;
                if (ss->size >= ss->capacity)
                {
                    return 2;
                }
                else
                {
                    ss->data[ss->size] = *data;
                    ss->size ++;
                    return 0;
                }
                break;
            }
            case OPD:
            {
                opd_stack *ss = (opd_stack *)s;
                double *data = (double *)e;
                if (ss->size >= ss->capacity)
                {
                    return 2;
                }
                else
                {
                    ss->data[ss->size] = *data;
                    ss->size ++;
                    return 0;
                }
                break;
            }
            default:
                exit(EXIT_FAILURE);
                break;
        }
        return 3;
    }
}

void *pop(void *s, stack_type type)
{
    void *val;
    if (s == NULL)
    {
        return NULL;
    }
    else
    {
        switch (type)
        {
            case OPR:
            {
                opr_stack *ss = (opr_stack *)s;
                if (ss->size <= 0) { return NULL; } else { val = (void *)&ss->data[ss->size - 1];
                    ss->size --;
                }
                break;
            }
            case OPD:
            {
                opd_stack *ss = (opd_stack *)s;
                if (ss->size <= 0) { return NULL; } else { val = (void *)&ss->data[ss->size - 1];
                    ss->size --;
                }
                break;
            }
            default:
                return NULL;
        }
        return val;
    }
}

void *top(void *s, stack_type type)
{ 
    void *val;
    if (s == NULL)
    {
        return NULL;
    }
    else
    {
        switch (type)
        {
            case OPR:
            {
                opr_stack *ss = (opr_stack *)s;
                if (ss->size <= 0) { return NULL; } else { val = (void *)&ss->data[ss->size - 1];
                }
                break;
            }
            case OPD:
            {
                opd_stack *ss = (opd_stack *)s;
                if (ss->size <= 0) { return NULL; } else { val = (void *)&ss->data[ss->size - 1];
                }
                break;
            }
            default:
                return NULL;
        }
        return val;
    }
}

int empty(void *s, stack_type type)
{
    if (s == NULL)
    {
        return 1;
    } 
    else
    {
        switch (type)
        {
            case OPR:
            {
                opr_stack *ss = (opr_stack *)s;
                if (ss->size == 0)
                {
                    return 1;
                }
                else
                {
                    return 0;
                }
                break;
            }
            case OPD:
            {
                opd_stack *ss = (opd_stack *)s;
                if (ss->size == 0)
                {
                    return 1;
                }
                else
                {
                    return 0;
                }
                break;
            }
            default:
                exit(EXIT_FAILURE);
                break;
        }
    }
}

int size(void *s, stack_type type)
{
    if (s == NULL)
    {
        return -1;
    }
    else
    {
        switch (type)
        {
            case OPR:
            {
                opr_stack *ss = (opr_stack *)s;
                return ss->size;
                break;
            }
            case OPD:
            {
                opd_stack *ss = (opd_stack *)s;
                return ss->size;
                break;
            }
            default:
                exit(EXIT_FAILURE);
                break;
        }
    }
}

double evaluate(char *expr)
{
    if (expr == NULL)
    {
        return 0.0;
    }

    trim(expr);

    int index = 0;
    double num;
    char op;
    opr_stack *opr;
    opd_stack *opd;

    opr = (opr_stack *)init_stack(OPR);
    opd = (opd_stack *)init_stack(OPD);

    op = '\0';
    push(opr, OPR, &op);

    while (!empty(opr, OPR))
    {
        if (isdigit(expr[index]))
        {
            num = readnum(expr, &index);
            if ( 0 != push(opd, OPD, &num))
            {
                fprintf(stderr, "Error push\n");
                exit(EXIT_FAILURE);
            }
        }
        else
        {
            switch (cmp_opr(expr[index], *(char *)top(opr, OPR)))
            {
                case '=':
                    pop(opr, OPR);
                    index++;    
                    break;
                case '>':
                    push(opr, OPR, &expr[index]);
                    index++;    
                    break;
                case '<':
                {
                    double opd1, opd2, val;
                    char op;
                    if (size(opd, OPD) < 2)
                    {
                        fprintf(stderr, "Error expression.\n");
                        exit(EXIT_FAILURE);
                    }
                    opd2 = *(double *)pop(opd, OPD);
                    opd1 = *(double *)pop(opd, OPD);
                    op = *(char *)pop(opr, OPR);
                    val = cal(opd1, opd2, op);
                    push(opd, OPD, &val);
                }
                    break;
                default:
                    fprintf(stderr, "Error expression.\n");
                    exit(EXIT_FAILURE);
                    break;
            }
        }
    }

    if (!empty(opd, OPD))
    {
        double val = *(double *)pop(opd, OPD);
        free_stack(opr);
        free_stack(opd);
        return val;
    }
    else
    { 
        free_stack(opr);
        free_stack(opd);
        fprintf(stderr, "Error expression.\n");
        exit(EXIT_FAILURE);
    }
}

double readnum(const char *p, int *pos)
{
    double result;
    sscanf(p + *pos, "%lf", &result);
    int flag = 0;
    while (p[*pos] && (isdigit(p[*pos]) || (flag == 0 && p[*pos] == '.')))
    {
        if (p[*pos] == '.')
        {
            flag = 1;
        }
        (*pos) ++;
    }
    return result;
}

char cmp_opr(char cur, char top)
{
    static char pri[SIGN_NUM][SIGN_NUM] = {
    /* top    +    -    *    /    ^    (    )    \0  */
    /* cur */
    /* + */ {'<', '<', '<', '<', '<', '>', ' ', '>'},
    /* - */ {'<', '<', '<', '<', '<', '>', ' ', '>'},
    /* * */ {'>', '>', '<', '<', '<', '>', ' ', '>'},
    /* / */ {'>', '>', '<', '<', '<', '>', ' ', '>'},
    /* ^ */ {'>', '>', '>', '>', '<', '>', ' ', '>'},
    /* ( */ {'>', '>', '>', '>', '>', '>', ' ', '>'},
    /* ) */ {'<', '<', '<', '<', '<', '=', ' ', ' '},
    /* \0 */{'<', '<', '<', '<', '<', '<', ' ', '='}
    };

    Operator o1, o2;
    switch (cur)
    {
        case '+':
            o1 = ADD;
            break;
        case '-':
            o1 = SUB;
            break;
        case '*':
            o1 = MUL;
            break;
        case '/':
            o1 = DIV;
            break;
        case '^':
            o1 = POW;
            break;
        case '(':
            o1 = L_P;
            break;
        case ')':
            o1 = R_P;
            break;
        case '\0':
            o1 = EOE;
            break;
        default:
            exit(EXIT_FAILURE);
            break;
    }

    switch (top)
    {
        case '+':
            o2 = ADD;
            break;
        case '-':
            o2 = SUB;
            break;
        case '*':
            o2 = MUL;
            break;
        case '/':
            o2 = DIV;
            break;
        case '^':
            o2 = POW;
            break;
        case '(':
            o2 = L_P;
            break;
        case ')':
            o2 = R_P;
            break;
        case '\0':
            o2 = EOE;
            break;
        default:
            exit(EXIT_FAILURE);
            break;
    }
    return pri[o1][o2];

}

double cal(double d1, double d2, char op)
{
    switch (op)
    {
        case '+':
            return d1 + d2;
            break;
        case '-':
            return d1 - d2;
            break;
        case '*':
            return d1 * d2;
            break;
        case '/':
            return d1 / d2;
            break;
        case '^':
            return pow(d1, d2);
            break;
        default:
            fprintf(stderr, "Operator error!\n");
            exit(EXIT_FAILURE);
            break;
    }
}

char *trim(char *s)
{
    char *cur, *p;
    cur = p = s;
    while (*p)
    {
        if (*p != ' ' && *p != '\t')
        {
            *cur++ = *p++;
        }
        else
        {
            p++;
        }
    }
    *cur = *p;
    return s;
}


如有疑问欢迎进行讨论。

(完)

如无特别说明,本站文章皆为原创,若要转载,务必请注明以下原文信息:
日志标题:《表达式求值-C语言实现》
日志链接:http://furzoom.com/expression-evaluation/
博客名称:枫竹梦

【上一篇】
【下一篇】

发表评论

插入图片

NOTICE1:请申请gravatar头像,没有头像的评论可能不会被回复!

回到顶部