调度场算法

表达式计算

一个看了就会写的图例

伪代码

对于一个仅含四则运算的表达式，我们可以通过这样操作把它变成后缀表达式

• 当还有记号可以读取时：
  
  • 读取一个记号。
  • 如果这个记号表示一个数字，那么将其添加到输出队列中。
  • 如果这个记号表示一个操作符，记做o1，那么：
    
    • 只要存在另一个记为o2的操作符位于栈的顶端，并且
      
      • 如果o1的运算符优先级要小于或者等于o2的优先级，那么
      • 将o2从栈的顶端弹出并且放入输出队列中（循环直至以上条件不满足为止）；
    • 然后，将o1压入栈的顶端。
  • 如果这个记号是一个左括号，那么就将其压入栈当中。
  • 如果这个记号是一个右括号，那么：
    
    • 从栈当中不断地弹出操作符并且放入输出队列中，直到栈顶部的元素为左括号为止。
    • 将左括号从栈的顶端弹出，但并不放入输出队列中去。
    • 如果在找到一个左括号之前栈就已经弹出了所有元素，那么就表示在表达式中存在不匹配的括号。
• 当再没有记号可以读取时：
  
  • 如果此时在栈当中还有操作符：
    
    • 如果此时位于栈顶端的操作符是一个括号，那么就表示在表达式中存在不匹配的括号。
    • 将操作符逐个弹出并放入输出队列中。
• 退出算法。

对于一个后缀表达式，我们可以这样计算它

• 当还有记号可以读取时：
  
  • 读取一个记号。
  • 如果这个记号表示一个数字，那么将其添加到栈中。
  • 如果这个记号表示一个操作符，记做o1，那么：
    
    • 从栈中取出该操作符对应数量的操作数
    • 计算操作符
    • 将计算所得的值入栈
• 当再没有记号可以读取时：
  
  • 如果此时在栈当中还有数：
    
    • 错误输入
  • 如果此时栈内只剩一个数
    
    • 这个值就是整个计算式的结果
• 退出算法。

注意到前算法的输出队列和后算法的入栈顺序相同，那么让两个算法同时进行就是计算表达式了。

轻松简单的实现

/*
    Author: Scarlet
*/
#include <stdio.h>
#include <ctype.h>
#include <string.h>
char ops[4] = "+-*/", S[1000];
int st[1000], tp, TP;
double ST[1000];
int getnxt(int *x, int *i)
{
    char ch = S[*i];
    int _[233], __[233];
    _['('] = 2, _[')'] = 3, _['+'] = 4, _['-'] = 4, _['*'] = 4, _['/'] = 4;
    __['('] = 0, __[')'] = 0, __['+'] = 0, __['-'] = 1, __['*'] = 2, __['/'] = 3;
    if (isdigit(ch))
    {
        for (*x = 0; isdigit(S[*i]); ++*i)
            *x = *x * 10 + S[*i] - 48;
        return 1;
    }
    else
        return *x = __[ch], ++*i, _[ch];
}
void prt(int op,int x)//后缀表达式转值
{
    if(op==0)
    {
        printf("%d ", x);
        ST[TP++] = (double)x;
    }
    else
    {
        printf("%c ", ops[x]);
        double Y = ST[TP - 1], X = ST[TP - 2];TP--;
        if (x == 0)
            ST[TP - 1] = X + Y;
        else if(x==1)
            ST[TP - 1] = X - Y;
        else if(x==2)
            ST[TP - 1] = X * Y;
        else
            ST[TP - 1] = X / Y;
    }
}
int main()
{
    freopen("w.in", "r", stdin);
    scanf("%s", S);
    int L = strlen(S);
    for (int i = 0; i < L;)
    {
        int x, op = getnxt(&x, &i);
        if (op == 1)
            prt(0, x);
        else if (op == 4)
        {
            for (; tp && st[tp - 1] / 2 >= x / 2;)
                prt(1, st[--tp]);
            st[tp++] = x;
        }
        else if (op == 2)
            st[tp++] = -2;
        else
            for (tp--; tp && st[tp] != -2;)
                prt(1, st[tp--]);
    }
    for (; tp;)
        prt(1, st[--tp]);
    printf("\n%lf\n", ST[0]);
    return 0;
}

小结

这也太强了吧QAQ

惊了，怕是大学里学的第一个算法= =