在进行顺序计算时保持操作顺序

Question

我正在花费我的晚上从Kattis处理一些编程问题。有一部分问题4 thought，我卡住了。

给出一个数字，该程序应该返回4个数据之间所需的运算（+， - ，*或/）以实现该数字。

例如，输入

9 

会导致输出

4 + 4 + 4/4 = 9 

我的解决方案（效率不高，但是简单）是评估所有可能的方式向运营商结合上面看如果任何组合达到想要的结果。

要做到这一点，我写了下面的功能。它需要一组字符串，它们是要评估的运算符（uo[3]，可能看起来像{+, /, *}），并且需要的结果为整数（expRes）。

bool check(char uo[3], int expRes) { 
    int res = 4; 
    for(int oPos = 2; oPos >= 0; oPos--) { 
     switch (uo[oPos]) { 
      case '+' : res += 4; break; 
      case '-' : res -= 4; break; 
      case '*' : res *= 4; break; 
      case '/' : res /= 4; break; 
     } 
    } 
    return res == expRes;  
} 

我意识到这种“顺序”方法带来一个问题：它不遵循操作顺序。如果我打电话给 uo = {+, -, /} 和 expRes = 7这个函数，它会返回false，因为4 + 4 = 8,8-4 = 4,4/4 = 1. 真正的答案显然是真的，因为4 + 4 - 4/4 = 7.

你们有没有想过重写函数的方法，以便评估遵循操作顺序？

在此先感谢！

Answer 1

如果你看看它，这是一个简单的问题。

你被四个4和3个操作员限制在中间，那你已经知道你的搜索空间了。因此，一种解决方案是生成完整的搜索空间，即O（n^3）= 4^3 = 64个总方程，其中n是运算符的数量。将这些解决方案的答案保留为<key, value>对，以便查找测试用例的输入为O（1）。

明智的你会做。

1. 生成完整的序列，并将其存储为键，值对
2. 接受输入从测试用例
3. 检查是否存在的关键，如果是打印顺序，否则打印序列不存在
4. 解将采取64点* 1000点的操作，其可以容易地与在第二计算，并能避免时间超出限制的错误，通常这些比赛在代码形式具有

（大部分是不完全的）：

// C++ Syntax 
map<int, string> mp; 

void generateAll() { 
    // generate all equations 
} 

void main() { 
    generateAll(); 

    int n, t; scanf("%d", &t); 
    while (t--) { 
     scanf("%d", &n); 

     if (mp.find(n) != mp.end()) 
      // equation exists to the input 
     else 
      // equation doesn't exist for the input 
    } 
}