c语言表达式求值

1.问题描述

请写一个整数计算器，支持加减乘三种运算和括号。

2.源码实现

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

enum operator {
    OPT_ADD,
    OPT_SUB,
    OPT_MUL
};

struct token {
    int type;
    int value;
};

int get_opt_type(char c)
{
    switch(c)
    {
        case '+': return OPT_ADD;
        case '-': return OPT_SUB;
        case '*': return OPT_MUL;
    }

    return 0;
}

int print_tokens(struct token *tokens, int n)
{
    int i;

    for(i=0; i<n; i++)
    {
        if(tokens[i].type == 1)
        {
            printf("%d ", tokens[i].value);
        }
        else if(tokens[i].type == 2)
        {
            switch(tokens[i].value)
            {
                case OPT_ADD:
                    printf("%c ", '+');
                    break;

                case OPT_SUB:
                    printf("%c ", '-');
                    break;

                case OPT_MUL:
                    printf("%c ", '*');
                    break;
            }
        }
    }

    printf("\n");
}

int get_number(char *s, int *v)
{
    int i = 0;

    if(s[i] == '-')
    {
        i++;
    }

    while(s[i] >= '0' && s[i] <= '9')
    {
        i++;
    }

    *v = atoi(s);

    return i-1;
}

int eval(struct token *tokens, int n)
{
    int *number = (int *)malloc(sizeof(int) * n);
    int j = 0;
    int i = 0;
    int u = 0;
    int res = 0;

    while(i < n)
    {
        if(tokens[i].type == 1)
        {
            number[j++] = tokens[i].value;
        }
        else if(tokens[i].type == 2)
        {
            if(tokens[i].value == OPT_ADD)
            {
                number[j-2] += number[j-1];
            }
            else if(tokens[i].value == OPT_SUB)
            {
                number[j-2] -= number[j-1];
            }
            else if(tokens[i].value == OPT_MUL)
            {
                number[j-2] *= number[j-1];
            }

            j--;
        }

        i++;
    }

    res = number[0];

    free(number);

    number = NULL;

    return res;
}

int solve(char *s)
{
    struct token stack[100];
    char tokens[100];
    int u = 0;
    int v = 0;
    int i;
    int j = 0;
    int res = 0;

    /*1.初始化两个栈, 中间结果栈和运算符栈*/
    memset(stack, 0x00, sizeof(stack));
    memset(tokens, 0x00, sizeof(tokens));

    /*2.从左至右扫描中缀表达式*/
    for(i=0; s[i]!=0x00; i++)
    {
        /*3.遇到操作数时, 将其压入中间结果栈*/
        if(s[i] >= '0' && s[i] <= '9')
        {
            stack[u].type = 1;
            i += get_number(s+i, &(stack[u].value));
            u++;
        }
        /*4.遇到运算符时, 比较优先级*/
        else if(s[i] == '-')
        {
            /*如果运算符栈为空, 或运算符栈顶为左括号, 则将此运算符入栈*/
            if(v == 0 || tokens[v-1] == '(')
            {
                tokens[v++] = s[i];
            }
            else
            {
                stack[u].type = 2;
                stack[u].value = get_opt_type(tokens[v-1]);
                tokens[v-1] = s[i];
                u++;
            }
        }
        else if(s[i] == '+')
        {
            if(v == 0 || tokens[v-1] == '(')
            {
                tokens[v++] = s[i];
            }
            else
            {
                stack[u].type = 2;
                stack[u].value = get_opt_type(tokens[v-1]);
                tokens[v-1] = s[i];
                u++;
            }
        }
        else if(s[i] == '*')
        {
            /*如果运算符优先级比栈顶运算符优先级高, 则将此运算符入栈*/
            if(v == 0 || tokens[v-1] == '(' || tokens[v-1] == '+' || tokens[v-1] == '-')
            {
                tokens[v++] = s[i];
            }
            /*否则, 将栈顶元素弹出入中间结果栈, 再将运算符入运算符栈*/
            else
            {
                stack[u].type = 2;
                stack[u].value = get_opt_type(tokens[v-1]);
                tokens[v-1] = s[i];
                u++;
            }
        }
        /*5.如果遇到左括号, 左括号入栈*/
        else if(s[i] == '(')
        {
            tokens[v++] = s[i];
        }
        /*6.如果遇到右括号, 依次弹出栈顶的运算符到中间结果栈直到遇到左括号*/
        else if(s[i] == ')')
        {
            while(tokens[v-1] != '(')
            {
                stack[u].type = 2;
                stack[u].value = get_opt_type(tokens[v-1]);
                u++;
                v--;
            }

            v--;
        }
    }

    /*7.依次弹出栈顶的运算符到中间结果栈*/
    while(v > 0)
    {
        stack[u].type = 2;
        stack[u].value = get_opt_type(tokens[v-1]);
        u++;
        v--;
    }

    /*8.计算逆波兰表达式的值*/
    res = eval(stack, u);

    return res;
}

int main()
{
    char *s = "(2*(3-4))*5";
    int n = -1;
    int res;

    res = solve(s);

    printf("%d\n", res);

    return 0;
}

3.编译源码

$ gcc -o test test.c -std=c89

4.运行及其结果

$ ./test
-10