pro.c

字符串形式的表达式求值算法

// 表达式求值
// 2007-09-17
// 算法3.3 p52
// 示例，假设输入表达式语法正确，暂支持10以内的数字运算

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "stack.h"

typedef struct _optr_pre
{
    char *pre;
}optr_pre;


// 运算符优先级列表,
optr_pre g_table[7*7] = 
{
    "++>", "+->", "+*<", "+/<", "+(<", "+)>", "+#>",
    "-+>", "-->", "-*<", "-/<", "-(<", "-)>", "-#>",
    "*+>", "*->", "**>", "*/>", "*(<", "*)>", "*#>",
    "/+>", "/->", "/*>", "//>", "/(<", "/)>", "/#>",

    "(+<", "(-<", "(*<", "(/<", "((<", "()=", "(#!",   // ( 为第一个运算符时优先级最低
    ")+>", ")->", ")*>", ")/>", ")(!", "))>", ")#>",   // ) 为第一个运算符时优先级最高
    "#+<", "#-<", "#*<", "#/<", "#(<", "#)!", "##=",   // # 为开头结尾符,#在前时优先级别最低
};


typedef int  operand;  // 运算数
typedef char operator; // 运算符
typedef char priority; // 优先级

#define ISNUM(a)  (('0'<=a)&&(a<='9'))

// 字符串比较函数
int STRNCMPI(char *str1, char *str2, unsigned maxlen)
{
    unsigned i=0;
    while(*str1 && *str2 && i++<maxlen)
    {
        if (*str1 != *str2)
            return (*str1 - *str2)?1:-1;
        str1++;str2++;
    }
    return 0;
}

priority Precede(operator a, operator b)
{
    int i;
    char temp[3] = {0};

    temp[0] = a;
    temp[1] = b;

    for(i=0;i<49;i++)
    {
        if (0 == STRNCMPI(temp, g_table[i].pre, 2))
            return *(g_table[i].pre+2);
    }
    return ' ';
}

operand caculate(operand a, operand b, operator c)
{
    switch(c)
    {
        case '+':return a+b;
        case '-':return a-b;
        case '*':return a*b;
        case '/':return a/b;
        default:return 0;
    }
}

int EvaluateExpression()
{
    SqStack optr, opnd;
    char c,top = 0;
    InitStack(&opnd, sizeof(operand));  // 初始化运算数栈
    InitStack(&optr, sizeof(operator)); // 初试化运算符栈
    c = '#';
    Push(&optr, &c);

    c = getchar();
    // 当运算符栈顶和输入符都为#的时候，运算结束
    while((c != '#') || (top != '#'))
    {
        if ISNUM(c)
        {
            operand num = c - '0';
            // 数字压栈,等待输入
            Push(&opnd, &num);
            c = getchar();
        }
        else
        {
            // 将栈顶运算符与输入运算符比较优先级
            operator topop;
            GetTop(&optr, &topop);
            switch(Precede(topop, c))
            {
                case '<':
                {
                    // 运算符压栈，继续等输入
                    Push(&optr, &c);
                    c = getchar();
                    break;
                }
                case '=':
                {
                    // 括号相对的情况，去掉括号
                    Pop(&optr, &c);
                    c = getchar();
                    break;
                }
                case '>':
                {
                    //
                    operand  topnd,secnd,result; // 取栈顶的前两个操作数
                    Pop(&optr, &topop);
                    Pop(&opnd, &topnd);
                    Pop(&opnd, &secnd);
                    result = caculate(secnd, topnd, topop);
                    Push(&opnd, &result); // 运算结果压栈
                    break;
                }
                default:
                    return -1;
            }
        }

        // 取栈顶运算符
        if (!GetTop(&optr, &top))
            return -1;
    }

    {   
        operand result;
        GetTop(&opnd, &result);
        printf("result is %d \n", result);
    }

    DestroyStack(&opnd);
    DestroyStack(&optr);
    return 0;
}


int main()
{
    while(1)
    {
        EvaluateExpression();
    }
}