0

什么是从后缀转换为中缀的好算法？我已经搜索和搜索，但我只得到从中缀转换为后缀的算法。它们将是非常相似的算法，对吗？我也想加入括号。例如，(((13 - 1) / 2)(3 + 5))。谢谢！

4

4 回答 4

5

这是后缀版本：-

13 1 - 2 / 3 5 + *

要进行转换，请像普通的后缀解析器一样解析它，但将元素作为字符串存储在堆栈中，而不是作为值：-

"13"
"1"
"-"

当你得到一个像上面一样的运算符时，转换为单个字符串并在它周围加上括号：-

"(13-1)"

继续：-

"(13-1)"
"2"
"/"

变成：-

"((13-1)/2)"

继续：-

"((13-1)/2)"
"3"
"5"
"+"

变成：-

"((13-1)/2)"
"(3+5)"

最后：-

"((13-1)/2)"
"(3+5)"
"*"

最终为： -

"((13-1)/2)*(3+5)"

您可以将“*”视为特殊情况并从组合版本中省略它。

于 2013-09-27T14:24:19.890 回答
1

这将是我的方法

while(input.hasNext()) {
   symbol = input.readNextSymbol(); // read the whole token
   if (symbol is operand) {
      stack.push(symbol)
   } else { // the symbol is an operator
      if (stack.count < 2) {
          ERROR too few operands
      } else {
         op2 = stack.pop();
         op1 = stack.pop();
         piece = "("+op1+symbol+op2+")";
         stack.push(piece);
      }      
   }
}

if (stack.count == 1) {
   stack.pop() is the INFIX
} else {
   ERROR
}

当然，如果要考虑一元运算符，则条件必须更加结构化以考虑具有单个元素的堆栈

于 2013-09-27T14:28:59.100 回答
1

我们从一个空堆栈开始。假设后缀表达式是正确的：

  • 读取原子标记并将它们放入堆栈
  • 当您到达一个运算符时，从堆栈中弹出 n 个元素，其中 n 是运算符的数量，正确格式化它，将括号放在它周围并将分辨率推回堆栈
  • 当没有内容可读取时，堆栈应该只包含一个带有结果的元素

例如 ：

输入 ：2,3,+,5,-,8,*

每个步骤之后的堆栈包含：

 2
 2,3
 (2+3)
 (2+3),5
 ((2+3)-5)
 ((2+3)-5),8
 (((2+3)-5)*8)
于 2013-09-27T14:26:18.453 回答
0

以下是上述算法的完整 Ruby 实现：

#!/usr/bin/env ruby

parts = gets.strip.split(/ +/)

stack = [ ]

parts.each do |part|
  if part =~ /\D/  # it's a binary operation
    right_operand = stack.pop
    left_operand = stack.pop
    stack.push("(#{left_operand} #{part} #{right_operand})")
  else             # it's a number
    stack.push(part)
  end
end

if stack.size == 1
  result = stack[0][1..-2]  # remove outer parentheses
  puts result
  exit(0)
else
  puts "parse error, stack does not contain exactly one element"
  exit(1)
end

像这样使用：

echo '13 1 - 2 / 3 5 + *' | ruby postfix-to-infix.rb

此示例产生结果：

((13 - 1) / 2) * (3 + 5)
于 2015-07-09T16:22:04.730 回答