jjzjj

c++ - 表达式转换问题

coder 2024-02-21 原文

假设我们有以下语句:s = 3 * a * b - 2 * c，其中 s, a, b 和 c 是变量。此外，我们使用了 Shunting Yard构建算法 RPN表达式，所以现在我们可以为变量 a、b 和 c 赋值，并使用简单的方法计算 s 值RPN 评估器。

但是，问题是我应该能够计算任何变量 a、b 或 c 的值设置了其他变量。

因此，我需要以某种方式转换现有表达式以获得一组表达式:

a = (s + 2 * c) / (3 * b)
b = (s + 2 * c) / (3 * a)
c = (3 * a * b - s) / 2

如何根据一个原始语句生成这样的表达式？是否有解决此类问题的标准方法？

约束:

  1. 一组可用的运算符:+、-、*、/，包括一元 + 和 -
  2. 运算符 *、/ 和 = 两边不能有相同的变量(例如 s = a * a 或 s = a + s 是 Not Acceptable )

谢谢

最佳答案

先看这个:Postfix notation to expression tree将您的 RPN 转换为树。

一旦你有了等式 left expression = right expression 将其更改为 left expression - right expression = 0 并创建一个 left expression - right expression 树 通过调车场和上面的答案。因此，当您评估树时，您必须得到答案为 0。

现在根据您的限制，观察如果变量(例如 x)未知，则结果表达式将始终采用以下形式

(ax + b)/(cx + d) 其中 a、b、c、d 将取决于其他变量。

您现在可以递归地将表达式计算为元组 (a,b,c,d)。

最后，你会解出线性方程

(ax + b)/(cx + d) = 0 给出 x = -b/a

这样您就不必为每个变量计算单独的表达式。一个表达式树就足够了。给定其他变量，您只需递归计算元组 (a,b,c,d)，最后求解线性方程。

(不完整的)伪代码将是

TupleOrValue Eval (Tree t) {

       if (!t.ContainsVariable) {
           blah;
           return value;
       }

       Tuple result;

       if (t.Left.ContainsVariable) {
            result = Eval(t.Left);  
            value = Eval(t.Right);

            return Compose(t.Operator, result, value);      
       } else {
            result = Eval(t.Right);  
            value = Eval(t.Left);

            return Compose(t.Operator, result, value);      
       }
}

Tuple Compose(Operator op, Tuple t, Value v) {

    switch (op) {

        case 'PLUS': return new Tuple(t.a + v*t.c, t.b + v*t.d, t.c, t.d);
                    // (ax+b)/(cx+d) + v = ( (a + vc)x + b + dv)/(cx + d)
        // blah
    }
}

举个例子，如果表达式是x+y-z = 0。树将是

     +
    /  \
   x    -
       / \
       y  z

对于 y=5 和 z=2。

Eval (t.Right) 将返回 y-z = 3，因为该子树不包含 x。

Eval(t.Left) 将返回对应于 (1x + 0)/(0x + 1) 的 (1,0,0,1)。注意:上面的伪代码是不完整的。

现在将 (1,0,0,1) 与值 3 组合将得到 (1 + 3*0, 0 + 3*1, 0, 1) = (1,3,0,1 ) 对应于 (x + 3)/(0x + 1)。

现在，如果你想解决这个问题，你可以将 x 设为 -b/a = -3/1 = -3

我会留下原来的答案:

一般来说这是不可能的。

例如考虑表达式

x*x*x*x*x + a*x*x*x*x + b*x*x*x + c*x*x + d*x = e

得到x的表达式基本上对应于求多项式的根

x5 + ax4 + bx3 + cx2 + dx -e

如果您想使用 +、-、/、* 和 n 次根，这已被证明通常是不可能的。参见 Abel Ruffini定理。

是否有一些您忘记提及的限制可能会简化问题？

关于c++ - 表达式转换问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5757282/

amp43codeexpressionsectionc++algorithmtransform

有关c++ - 表达式转换问题的更多相关文章

  1. ruby-on-rails - 在 Rails 中将文件大小字符串转换为等效千字节 - 2

    我的目标是转换表单输入，例如“100兆字节”或“1GB”，并将其转换为我可以存储在数据库中的文件大小(以千字节为单位)。目前，我有这个:defquota_convert@regex=/([0-9]+)(.*)s/@sizes=%w{kilobytemegabytegigabyte}m=self.quota.match(@regex)if@sizes.include?m[2]eval("self.quota=#{m[1]}.#{m[2]}")endend这有效，但前提是输入是倍数(“gigabytes”，而不是“gigabyte”)并且由于使用了eval看起来疯狂不安全。所以，功能正常，

  2. ruby - 使用 ruby​​ 将 HTML 转换为纯文本并维护结构/格式 - 2

    我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h

  3. ruby - 在 64 位 Snow Leopard 上使用 rvm、postgres 9.0、ruby 1.9.2-p136 安装 pg gem 时出现问题 - 2

    我想为Heroku构建一个Rails3应用程序。他们使用Postgres作为他们的数据库，所以我通过MacPorts安装了postgres9.0。现在我需要一个postgresgem并且共识是出于性能原因你想要pggem。但是我对我得到的错误感到非常困惑当我尝试在rvm下通过geminstall安装pg时。我已经非常明确地指定了所有postgres目录的位置可以找到但仍然无法完成安装:$envARCHFLAGS='-archx86_64'geminstallpg--\--with-pg-config=/opt/local/var/db/postgresql90/defaultdb/po

  4. ruby - 通过 rvm 升级 ruby​​gems 的问题 - 2

    尝试通过RVM将RubyGems升级到版本1.8.10并出现此错误:$rvmrubygemslatestRemovingoldRubygemsfiles...Installingrubygems-1.8.10forruby-1.9.2-p180...ERROR:Errorrunning'GEM_PATH="/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/ruby-1.9.2-p180@global:/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/rub

  5. ruby - 将数组的内容转换为 int - 2

    我需要读入一个包含数字列表的文件。此代码读取文件并将其放入二维数组中。现在我需要获取数组中所有数字的平均值，但我需要将数组的内容更改为int。有什么想法可以将to_i方法放在哪里吗？ClassTerraindefinitializefile_name@input=IO.readlines(file_name)#readinfile@size=@input[0].to_i@land=[@size]x=1whilex 最佳答案 只需将数组映射为整数:@land边注如果你想得到一条线的平均值，你可以这样做:values=@input[x]

  6. ruby - 将散列转换为嵌套散列 - 2

    这道题是thisquestion的逆题.给定一个散列，每个键都有一个数组，例如{[:a,:b,:c]=>1,[:a,:b,:d]=>2,[:a,:e]=>3,[:f]=>4,}将其转换为嵌套哈希的最佳方法是什么{:a=>{:b=>{:c=>1,:d=>2},:e=>3,},:f=>4,} 最佳答案 这是一个迭代的解决方案，递归的解决方案留给读者作为练习:defconvert(h={})ret={}h.eachdo|k,v|node=retk[0..-2].each{|x|node[x]||={};node=node[x]}node[

  7. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  8. ruby 正则表达式 - 如何替换字符串中匹配项的第 n 个实例 - 2

    在我的应用程序中，我需要能够找到所有数字子字符串，然后扫描每个子字符串，找到第一个匹配范围(例如5到15之间)的子字符串，并将该实例替换为另一个字符串“X”。我的测试字符串s="1foo100bar10gee1"我的初始模式是1个或多个数字的任何字符串，例如，re=Regexp.new(/\d+/)matches=s.scan(re)给出["1","100","10","1"]如果我想用“X”替换第N个匹配项，并且只替换第N个匹配项，我该怎么做？例如，如果我想替换第三个匹配项“10”(匹配项[2])，我不能只说s[matches[2]]="X"因为它做了两次替换“1fooX0barXg

  9. ruby - 通过 RVM (OSX Mountain Lion) 安装 Ruby 2.0.0-p247 时遇到问题 - 2

    我的最终目标是安装当前版本的RubyonRails。我在OSXMountainLion上运行。到目前为止，这是我的过程:已安装的RVM$\curl-Lhttps://get.rvm.io|bash-sstable检查已知(我假设已批准)安装$rvmlistknown我看到当前的稳定版本可用[ruby-]2.0.0[-p247]输入命令安装$rvminstall2.0.0-p247注意:我也试过这些安装命令$rvminstallruby-2.0.0-p247$rvminstallruby=2.0.0-p247我很快就无处可去了。结果:$rvminstall2.0.0-p247Search

  10. ruby - Fast-stemmer 安装问题 - 2

    由于fast-stemmer的问题，我很难安装我想要的任何ruby​​gem。我把我得到的错误放在下面。Buildingnativeextensions.Thiscouldtakeawhile...ERROR:Errorinstallingfast-stemmer:ERROR:Failedtobuildgemnativeextension./System/Library/Frameworks/Ruby.framework/Versions/2.0/usr/bin/rubyextconf.rbcreatingMakefilemake"DESTDIR="cleanmake"DESTDIR=

随机推荐