http://poj.org/problem?id=1686

大体思路是用某些数替换掉未知数,再套用表达式求值的模板。
但是这样不太严密,可以随机一些小数据重复计算几遍,看看运算结果是否相等。

(如果你有强迫症,不相信随机算法的话,可以参考matlab中simple()函数的实现)

PS:这题用ScriptEngine相当之方便(24行代码)
主要是eval(String str)这个函数,它可以直接执行你传入的表达式。

/*235ms,6236KB*/

import java.io.*;
import java.util.Scanner;
import javax.script.*;

public class Main {
    static Scanner cin = new Scanner(new BufferedInputStream(System.in));

    public static void main(String[] args) throws ScriptException {
        ScriptEngineManager factory = new ScriptEngineManager();
        ScriptEngine engine = factory.getEngineByName("JavaScript");
        int t = cin.nextInt();
        cin.nextLine();
        String s1, s2;
        while (t-- > 0) {
            s1 = cin.nextLine();
            s2 = cin.nextLine();
            for (char i = 'a'; i <= 'z'; ++i) {
                s1 = s1.replace("" + i, String.valueOf((int) i));
                s2 = s2.replace("" + i, String.valueOf((int) i));
            }
            System.out.println(engine.eval(s1).toString().equals(engine.eval(s2).toString()) ? "YES" : "NO");
        }
    }
}

正片:

/*0ms,200KB*/

const int mx = int(1e5) + 5;

stack<int> num;/// *在题意为double下改为double
stack<char> op;
int priv[127], val[27];

void init()
{
    while (!num.empty()) num.pop();
    //while (!op.empty()) op.pop();
    priv['+'] = priv['-'] = 3;
    priv['*'] = priv['/'] = 2;
    priv['^'] = 1; /// 幂运算
    priv['('] = 10; /// 特殊处理
}

int calc(int a, int b, char op)
{
    if (op == '+') return a + b;
    if (op == '-') return a - b;
    if (op == '*') return a * b;
    if (op == '/') return a / b; /// *在题意为double下使用
    //if (op == '^') return exp(log(a) * b); /// *在题意为double下使用
}

void calc()
{
    int y = num.top();
    num.pop();
    int x = num.top();
    num.pop();
    char tmpop = op.top();
    op.pop();
    num.push(calc(x, y, tmpop));
}

int calc(char *str)
{
    init();
    int x, y, i, n = strlen(str);
    char tmpop, last = 0;
    For(i, n)
    {
        if (isalpha(str[i])) num.push(str[i]);
        else if (isdigit(str[i]))
        {
            num.push(atoi(str + i)); /// *在题意为double下用atof
            for (; i + 1 < n && isdigit(str[i + 1]); ++i) ;
            //if (i + 1 < n && str[i + 1] == '.') for (++i; i + 1 < n && isdigit(str[i + 1]); ++i) ; /// *在题意为double下使用
        }
        else if (str[i] == '(') op.push('(');
        else if (str[i] == ')')
        {
            while (op.top() != '(') calc();
            op.pop(); /// 弹出'('
        }
        else if (str[i] == '-' && (last == 0 || last == '(')) num.push(0), op.push('-');
        else if (priv[str[i]])
        {
            while (!op.empty() && priv[op.top()] <= priv[str[i]]) calc(); /// 优先级高(priv[]小)的先运算
            op.push(str[i]); /// 压入当前运算符, 此时前面的高优先级运算已完成
        }
        else continue; /// 空格
        last = str[i];
    }
    while (!op.empty()) calc();
    return num.top();
}

char s[85],s2[85];

bool ok()
{
    gets(s);
    gets(s2);
    return calc(s) == calc(s2);
}

int main()
{
    int t;
    SI(t), getchar();
    while(t--) puts(ok() ? "YES" : "NO");
    return 0;
}

Comments

comments powered by Disqus