1

在作为函数的字符串输入给定的一个变量中求解线性方程的最有效算法是什么？例如，对于输入字符串：

“x + 9 – 2 - 4 + x = – x + 5 – 1 + 3 – x”

输出应为 1。

当我遇到字符串中的空格时，我正在考虑使用堆栈并将每个字符串标记推到它上面。如果输入是波兰语表示法，那么从堆栈中弹出数字以获得结果会更容易，但我不确定在这里采取什么方法。

这是一道面试题。

4

4 回答 4

11

一旦你计算出系数a和b方程，求解线性方程（我希望）对你来说非常容易a * x + b = 0。

因此，问题的困难部分是解析表达式并“评估”它以找到系数。您的示例表达式非常简单，它仅使用运算符 unary -、 binary -、 binary +。而且=，你可以特别处理。

从这个问题中不清楚解决方案是否还应该处理涉及二进制*and/或括号的表达式。我想知道面试问题是否有意：

  • 让你写一些简单的代码，或者
  • 在你写任何东西之前让你问问题的真正范围是什么。

两者都是重要的技能:-)

甚至可能是这个问题的意图：

  • 将那些有很多编写解析器经验的人（他们会以他们能写/打字的速度解决它）与那些没有编写解析器的人（他们可能在几分钟内很难解决它，至少没有一些提示）分开。

无论如何，为了满足未来更复杂的需求，解析算术表达式有两种常用方法：递归下降或 Dijkstra 的分流场算法。您可以查看这些，如果您只需要 1.0 版中的简单表达式，那么您可以使用 Dijkstra 算法的简化形式。然后，一旦您解析了表达式，就需要对其进行评估：使用线性表达式的值x并将其解释=为具有最低可能优先级的运算符，这意味着“减法”。结果是一个线性表达式x，等于0。

如果您不需要复杂的表达式，那么您可以在对它进行标记后直接从左到右评估这个简单的示例[*]：

x
x + 9
// set the "we've found minus sign" bit to negate the first thing that follows
x + 7 // and clear the negative bit
x + 3
2 * x + 3
// set the "we've found the equals sign" bit to negate everything that follows
3 * x + 3
3 * x - 2
3 * x - 1
3 * x - 4
4 * x - 4

最后，求解a * x + b = 0为x = - b/a。

[*] 示例标记化代码，在 Python 中：

acc = None
for idx, ch in enumerate(input):
    if ch in '1234567890':
        if acc is None: acc = 0
        acc = 10 * acc + int(ch)
        continue
    if acc != None:
        yield acc
        acc = None
    if ch in '+-=x':
        yield ch
    elif ch == ' ':
        pass
    else:
        raise ValueError('illegal character "%s" at %d' % (ch, idx))

替代示例标记化代码，也在 Python 中，假设标记之间总是有空格，如示例中所示。这将令牌验证留给解析器：

return input.split()
于 2013-04-29T08:02:42.540 回答
1

好的，您可以使用一些简单的伪代码来解决此问题

 function(stinrgToParse){
      arrayoftokens = stringToParse.match(RegexMatching);
      foreach(arrayoftokens as token)
      {
         //now step through the tokens and determine what they are
         //and store the neccesary information.
      }
      //Use the above information to do the arithmetic.
      //count the number of times a variable appears positive and negative
      //do the arithmetic.
      //add up the numbers both positive and negative. 
      //return the result.
 }
于 2013-04-29T07:47:06.553 回答
1

考虑：

from operator import add, sub
def ab(expr):
    a, b, op = 0, 0, add
    for t in expr.split():
        if   t == '+': op = add
        elif t == '-': op = sub
        elif t == 'x': a = op(a, 1)
        else         : b = op(b, int(t))
    return a, b

给定这样的表达式1 + x - 2 - x...将其转换为规范形式ax+b并返回一对系数(a,b)。

现在，让我们从方程的两个部分获得系数：

le, ri = equation.split('=')    
a1, b1 = ab(le)
a2, b2 = ab(ri)

最后求解平凡方程a1*x + b1 = a2*x + b2：

x = (b2 - b1) / (a1 - a2)

当然，这只解决了这个特定的例子，没有运算符优先级或括号。为了支持后者，您需要一个解析器，大概是一个递归下降解析器，这对于手动编码来说会更简单。

于 2013-04-29T10:47:09.700 回答
1

首先是解析字符串，识别各种标记（数字、变量和运算符），以便通过给运算符适当的优先级来形成表达式树。

正则表达式可以提供帮助，但这不是唯一的方法（诸如 boost::spirit 之类的语法解析器也很好，您甚至可以运行自己的：它都是“查找和追索”）。

然后可以操纵树，减少执行那些处理常量的操作的节点，并通过对变量相关的操作进行分组，相应地执行它们。

这会递归地进行，直到您保留一个变量相关节点和一个常量节点。

在这一点上，解决方案的计算很简单。

它们基本上是导致产生解释器或编译器的相同原则。

于 2013-04-29T07:58:54.703 回答