C++之四则运算表达式求值

 

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

#define inf float(0x3f3f3f3f)
#define maxsize 100

char priority[7] = {'+', '-', '*', '/', '(', ')', '#'};

char priority_relationship[7][7] = {
    {'>', '>', '<', '<', '<', '>', '>'}, 
    {'>', '>', '<', '<', '<', '>', '>'}, 
    {'>', '>', '>', '>', '<', '>', '>'}, 
    {'>', '>', '>', '>', '<', '>', '>'}, 
    {'<', '<', '<', '<', '<', '=', ' '}, 
    {'>', '>', '>', '>', ' ', '>', '>'}, 
    {'<', '<', '<', '<', '<', ' ', '='} 
};


typedef struct stacknode
{
    char data[maxsize];   // 压入栈里面的数据都是字符型，在进行运行时，记得将字符型数字转换为浮点型数字
    struct stacknode *next;
}stacknode, *linkstack;

void initstack(linkstack &s)
{// 构造一个空栈s，栈顶指针置空
    s = null;
}

void push(linkstack &s, char data[])
{// 在栈顶插入元素data
    stacknode *p;

    p = (stacknode *)malloc(sizeof(stacknode));  // 生成新的结点
    strcpy(p->data, data);  // 将新结点的数据域置为data
    p->next = s;    // 将新结点插入栈顶
    s = p;    // 修改栈顶指针为p
}

char *pop(linkstack &s)
{// 删除s的栈顶元素， 用data返回其值
    char data[maxsize];
    if(s == null) printf("错误！！！\n栈为空， 无法执行删除命令...");
    else
    {
        stacknode *p;

        strcpy(data, s->data);  // 将栈顶元素赋给data
        p = s;   // 用p临时保存栈顶元素的空间，以备释放
        s = s->next;   //修改栈顶指针 
        free(p);    // 释放原栈顶元素的空间
        return data;
    }
}

char *gettop(linkstack &s)
{
    if(s != null)
        return s->data;
    else
    {
        printf("错误！！！\n栈顶为空");
        return "0";
    }
}

float str_to_float(char *str)
{
    float num = 0;
    int state_1 = 0;
    int state_2 = 0;
    while(( *str != '\0' && *str >= '0' && *str <= '9') || *str == '.' || (*str == '-' && *(str + 1) != '\0'))
    {// 注意判断小数点和负号
        if(*str == '.') state_1 = 1;
        else if(*str == '-') state_2 = 1;
        else
        {
            if(state_1 == 0) num = num * 10 + (*str - '0');
            else
            {
                num += (*str - '0') * pow(0.1, state_1);
                state_1++;
            }
        }
        str++;
    }
    if(*str != '\0') return inf;
    else if(state_2 == 1)
    {
        return num * -1;
    }
    else return num;
}

char *float_to_str(float num)
{
    char str[maxsize];
    sprintf(str, "%.4f", num);  // 保留小数点后4位
    return str;
}

int get_index(char str[])
{
    for(int i = 0; i < 7; i++)
    {
        if(str[0] == priority[i]) return i;
    }
    printf("未找到匹配的字符\n");
}

char precede(char inside_data[], char input_data[])
{
    int inside_index = get_index(inside_data);
    int input_index = get_index(input_data);

    return priority_relationship[inside_index][input_index];
}

float operate(char a[], char theta[], char b[])
{//执行运算
    float a_num = str_to_float(a);
    float b_num = str_to_float(b);

    if(theta[0] == '+') return a_num + b_num;
    else if(theta[0] == '-') return a_num - b_num;
    else if(theta[0] == '*') return a_num * b_num;
    else if(theta[0] == '/') return a_num / b_num;
    else printf("错误！！！\n无该运算符");
}

float evaluateexpression()
{
    stacknode *opnd, *optr;
    char str[maxsize];
    char theta[maxsize];
    char a[maxsize];
    char b[maxsize];

    initstack(opnd);
    initstack(optr);
    push(optr, "#");

    scanf("%s", str);
    while(str[0] != '#' || gettop(optr)[0] != '#')
    {
        if(str_to_float(str) != inf)
        {
            push(opnd, str);
            scanf("%s", str);
        }
        else
        {
            switch (precede(gettop(optr), str))
            {
            case '<':
                push(optr, str);
                scanf("%s", str);
                break;
            case '>':
                strcpy(theta, pop(optr));
                strcpy(b, pop(opnd));
                strcpy(a, pop(opnd));
                char temp_str[maxsize];
                strcpy(temp_str, float_to_str(operate(a, theta, b)));
                push(opnd, temp_str);
                break;
            case '=':
                pop(optr);
                scanf("%s", str);
                break;
            default:
                printf("错误！！！\n该优先级不存在！！！");
            }
        }

    }

    return str_to_float(gettop(opnd));
}

int main(void)
{
    float num;

    num = evaluateexpression();
    printf("%f\n", num);

    printf("\n");
    system("pause");
}