NYOJ－35－表达式求值

描述
ACM队的mdd想做一个计算器，但是，他要做的不仅仅是一计算一个A+B的计算器，他想实现随便输入一个表达式都能求出它的值的计算器，现在请你帮助他来实现这个计算器吧。
比如输入：“1+2/4=”，程序就输出1.50（结果保留两位小数）

输入
第一行输入一个整数n，共有n组测试数据（n<10)。
每组测试数据只有一行，是一个长度不超过1000的字符串，表示这个运算式，每个运算式都是以“=”结束。这个表达式里只包含+-*/与小括号这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数。
数据保证除数不会为0

输出
每组都输出该组运算式的运算结果，输出结果保留两位小数。

样例输入
2
1.000+2/4=
((1+2)*5+1)/4=

样例输出
1.50
4.00

题目比较容易理解，就是实现四则运算。
说到四则运算，不得不提到逆波兰表示法，也就是后缀表示法。这种表示法不需要括号，对于9 + (3 - 1) x 3 + 10 ÷ 2用后缀表示法的样子则是：9 3 1 － 3 ＊＋ 10 2 ／＋。之所以叫后缀的原因是，所有的运算符号都是要在运算数字的后边出现，那么很容易的想到，我们平时写的式子，也就是第一个式子，是中缀表示法。

中缀表达式转后缀表达式规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或者优先级低于栈顶符号（乘除优先于加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止，这里我们需要一个栈来实现，用于符号的进栈出栈。

9 + (3 - 1) x 3 + 10 ÷ 2（中缀表达式） >>> 9 3 1 － 3 ＊＋ 10 2 ／＋（后缀表达式）

后缀表达式使用规则：从左到右遍历后缀表达式的每一个数字和符号，遇到是数字就进栈，遇到是符号，就当处于栈顶的两个数字出栈进行运算，运算结果进栈，一直到最终获得结果。

这里存在两个过程，
1.将中缀表达式转化为后缀表达式（栈用来进出运算符号）。
2.将后缀表达式进行运算得到结果（栈用来进出运算的数字）。

代码如下：

/* 不知道为啥一直WA，可是我试了很多数据都可以的，哎，头疼死了。暂且记下，来日再战，我需要静静。 后边的两个代码均是AC代码。 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INF 10000000
#define ADD INF + 1 //+
#define SUB INF + 2 //-
#define MUL INF + 3 //x
#define DIV INF + 4 //÷

char str[1005];     //原公式
int len;            //公式长度
char symbol[1000];   //运算符号栈
float suffix[1005]; //后缀式
float answer[1000];  //运算栈

//从s[*pc]开始获取一个浮点数
int StrToInt(char s[], int * pc, float *pout)
{
    char buf[100];
    int i = 0;

    if(s[*pc]<'0' || s[*pc]>'9')
        return 1;
    else
    {
        while((s[*pc] >= '0' && s[*pc] <= '9') || s[*pc] == '.')
        {
            buf[i] = s[*pc];
            (*pc)++;
            i++;
        }
        buf[i] = '\0';
        *pout = (float)atof(buf);
        return 0;
    }
}

void swi(int *key, char sym)
{
    switch (sym)
    {
        case '+':
            suffix[(*key)++] = ADD;
            break;
        case '-':
            suffix[(*key)++] = SUB;
            break;
        case '*':
            suffix[(*key)++] = MUL;
            break;
        case '/':
            suffix[(*key)++] = DIV;
            break;
    }
}

void perform(int suf, int *_key)
{
    float a = answer[(*_key)--];
    float b = answer[(*_key)];
    float c;
    switch (suf)
    {
        case (INF + 1):
            c = a + b;
            break;
        case (INF + 2):
            c = b - a;
            break;
        case (INF + 3):
            c = a * b;
            break;
        default:
            c = b / a;
            break;
    }
    answer[*_key] = c;
// printf("%.2f\n", answer[*_key]);
    return ;
}

int main()
{
    int T;
    scanf("%d", &T);

    while(T--)
    {
        scanf("%s", str);
        len = (int)strlen(str) - 1;
        int key = 0;
        int top = -1;
        float pout;
        //中缀式转后缀式
        for (int i = 0; i < len; )
        {
            if (!StrToInt(str, &i, &pout))
            {
                suffix[key++] = pout;
            }
            else if (top != -1 && str[i] == ')')
            {
                while (symbol[top] != '(')
                {
                    swi(&key, symbol[top--]);
                }
                i++;
                top--;
            }
            else if (top != -1 && (str[i] == '+' || str[i] == '-') && (symbol[top] == '*' || symbol[top] == '/'))
            {
                while (symbol[top] != '(' && top >= 0)
                {
                    swi(&key, symbol[top--]);
                }
                symbol[++top] = str[i++];
            }
            else if (top != -1 && (str[i] == '*' || str[i] == '/') && (symbol[top] == '*' || symbol[top] == '/'))
            {
                swi(&key, symbol[top]);
                symbol[top] = str[i++];
            }
            else
            {
                symbol[++top] = str[i++];
            }
        }
        while (top >= 0)
        {
            swi(&key, symbol[top--]);
        }

// for (int i = 0; i < key; i++)
// {
   
// printf("%f ", suffix[i]);
// }
// printf("\n");
        //后缀式运算
        int _key = -1;
        for (int i = 0; i < key; i++)
        {
            if (suffix[i] < INF)
            {
                answer[++_key] = suffix[i];
// printf("%.2f\n", answer[_key]);
            }
            else
            {
                perform((int)suffix[i], &_key);
            }
        }
        printf("%.2f\n", answer[0]);
    }
    return 0;
}

另外还有两种方法，第一种是将字符和数据分别入两个栈，然后根据优先级的比较，对数据栈顶的两个元素进行出栈操作然后进栈。

NYOJ－35－表达式求值

全站热榜