草庐IT

java - 在 Java 中解析算术表达式并从中构建树

coder 2023-05-14 原文

在给定算术表达式的情况下，我需要一些帮助来创建自定义树。比如说，你输入这个算术表达式:

(5+2)*7

结果树应如下所示:

    *
   / \
  +   7
 / \
5   2

我有一些自定义类来表示不同类型的节点，即 PlusOp、LeafInt 等。我不需要评估表达式，只需创建树，这样我以后就可以对其执行其他功能。 另外，否定运算符“-”只能有一个子，要表示“5-2”，必须输入为5 + (-2)。

需要对表达式进行一些验证，以确保每种类型的运算符都有正确的编号。对于参数/子项，每个左括号都伴随着一个右括号。

另外，我应该提一下我的 friend 已经编写了将输入字符串转换为 token 堆栈的代码，如果这对此有所帮助的话。

如果有任何帮助，我将不胜感激。谢谢:)

(我读到您可以编写语法并使用 antlr/JavaCC 等来创建解析树，但我不熟悉这些工具或编写语法，所以如果这是您的解决方案，我会如果您能为他们提供一些有用的教程/链接，我们将不胜感激。)

最佳答案

假设这是某种家庭作业，你想自己做......

我做过一次，你需要一个堆栈

所以你为这个例子做的是:

    parse    what to do?                Stack looks like
      (      push it onto the stack     (
      5      push 5                     (, 5
      +      push +                     (, 5, +
      2      push 2                     (, 5, +, 2
      )      evaluate until (           7            
      *      push *                     7, *
      7      push 7                     +7, *, 7
      eof    evaluate until top         49

“5”或“+”之类的符号可以只存储为字符串或简单对象，或者您可以将 + 存储为 +() 对象而不设置值并在评估时设置它们。

我认为这也需要优先顺序，所以我将描述它是如何工作的。

如果是:5 + 2 * 7

你必须推 5 推 + 推 2 下一个操作的优先级更高，所以你也推它，然后推 7。当你遇到 a ) 或文件结尾或优先级较低或相等的运算符时，你开始计算堆栈到前一个(或文件的开头。

因为您的堆栈现在包含 5 + 2 * 7，所以当您评估它时，您首先弹出 2 * 7 并将生成的 *(2,7) 节点插入堆栈，然后再次评估前三项堆栈(5 + *节点)所以树出来是正确的。

如果它以另一种方式排序:5 * 2 + 7，您将推送直到您到达具有“5 * 2”的堆栈，然后您将达到较低优先级 +，这意味着评估您现在所拥有的。您将 5 * 2 评估为 *node 并将其推送，然后您将继续推送 + 和 3，这样您就有了 *node + 7，此时您将评估它。

这意味着您有一个“最高当前优先级”变量，当您按下 +/- 时存储一个 1，当您按下 * 或/时存储一个 2，以及一个用于“^”的 3。这样您就可以只测试变量以查看下一个运算符的优先级是否为 < =="">

如果 ")"被认为是优先级 4，您可以将其视为其他运算符，但它会删除匹配的 "("，较低的优先级不会。

关于java - 在 Java 中解析算术表达式并从中构建树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4589951/

建树从中运算符section自定javaparsingtree

有关java - 在 Java 中解析算术表达式并从中构建树的更多相关文章

  1. Ruby 解析字符串 - 2

    我有一个字符串input="maybe(thisis|thatwas)some((nice|ugly)(day|night)|(strange(weather|time)))"Ruby中解析该字符串的最佳方法是什么？我的意思是脚本应该能够像这样构建句子:maybethisissomeuglynightmaybethatwassomenicenightmaybethiswassomestrangetime等等，你明白了......我应该一个字符一个字符地读取字符串并构建一个带有堆栈的状态机来存储括号值以供以后计算，还是有更好的方法？也许为此目的准备了一个开箱即用的库？

  2. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  3. ruby - 用逗号、双引号和编码解析 csv - 2

    我正在使用ruby​​1.9解析以下带有MacRoman字符的csv文件#encoding:ISO-8859-1#csv_parse.csvName,main-dialogue"Marceu","Giveittohimóhe,hiswife."我做了以下解析。require'csv'input_string=File.read("../csv_parse.rb").force_encoding("ISO-8859-1").encode("UTF-8")#=>"Name,main-dialogue\r\n\"Marceu\",\"Giveittohim\x97he,hiswife.\"\

  4. 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

  5. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/

  6. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

  7. ruby-on-rails - 我更新了 ruby​​ gems，现在到处都收到解析树错误和弃用警告! - 2

    简而言之错误:NOTE:Gem::SourceIndex#add_specisdeprecated,useSpecification.add_spec.Itwillberemovedonorafter2011-11-01.Gem::SourceIndex#add_speccalledfrom/opt/local/lib/ruby/site_ruby/1.8/rubygems/source_index.rb:91./opt/local/lib/ruby/gems/1.8/gems/rails-2.3.8/lib/rails/gem_dependency.rb:275:in`==':und

  8. java - 我的模型类或其他类中应该有逻辑吗 - 2

    我只想对我一直在思考的这个问题有其他意见，例如我有classuser_controller和classuserclassUserattr_accessor:name,:usernameendclassUserController//dosomethingaboutanythingaboutusersend问题是我的User类中是否应该有逻辑user=User.newuser.do_something(user1)oritshouldbeuser_controller=UserController.newuser_controller.do_something(user1,user2)我

  9. java - 什么相当于 ruby​​ 的 rack 或 python 的 Java wsgi？ - 2

    什么是ruby​​的rack或python的Java的wsgi？还有一个路由库。 最佳答案 来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht

  10. Observability：从零开始创建 Java 微服务并监控它 （二） - 2

    这篇文章是继上一篇文章“Observability：从零开始创建Java微服务并监控它（一）”的续篇。在上一篇文章中，我们讲述了如何创建一个Javaweb应用，并使用Filebeat来收集应用所生成的日志。在今天的文章中，我来详述如何收集应用的指标，使用APM来监控应用并监督web服务的在线情况。源码可以在地址 https://github.com/liu-xiao-guo/java_observability 进行下载。摄入指标指标被视为可以随时更改的时间点值。当前请求的数量可以改变任何毫秒。你可能有1000个请求的峰值，然后一切都回到一个请求。这也意味着这些指标可能不准确，你还想提取最小/

随机推荐