将Infix转换为前缀转换

Question

最近，我浏览了一些网站，将中缀转换成前缀符号，最后我被卷了起来。

我已经给出了我所做的步骤。。

例：-（1（2*3））（5*6）（7/8）

方法1：-（无需任何算法的手动转换）：-

Step1: (1+(*23)) + (*56) + (/78)  

Step2: (+1*23) + (*56) + (/78) 

Step3: +(+1*23)(*56) + (/78) 

Step4: +[+(+1*23)(*56)](/78) 

Step5: +++1*23*56/78            **--- Final Ans -----** 

方法2：-

根据现场情况http://scanftree.com/Data_Structure/infix-to-prefix

Step1: Reverse it:-
       ) 8 / 7 ( + ) 6 * 5 ( + ) ) 3 * 2 ( + 1 ( 

Step2: Replace the '(' by ')' and vice versa:
       ( 8 / 7 ) + ( 6 * 5 ) + ( ( 3 * 2 ) + 1 ) 

Step3: Convert the expression to postfix form:-
       8 7 / 6 5 * + 3 2 * 1 + + 

Step4: Reverse it
       + + 1 * 2 3 + * 5 6 / 7 8     --- Final Ans -----

所以，在这里我完全被绞死了。

请任何人提供以下方面的信息：-

1. 关于我在以上2种方法中哪里出错了
2. 哪个是正确答案

所以我可以更好地理解这个概念。

Answer 1

手动转换是正确的，因为当我们反转中缀表达式以计算前缀时，表达式的关联性从左到右到右到左变化，这在算法中没有考虑，并且经常被忽略。

示例：表达式：5-3-2：内缀到前缀（手动转换）（-5 3)-2 -(- 5 3) 2 - - 5 3 2

现在由算法（如果关联性没有改变）反向表达式：2-3-5

后缀： 2 3-5-

再次反向获得前缀：-5-3 2

现在看看，如果我们忽略了关联性，它会产生巨大的差异

现在，如果我们改变从左到右到右到左的联想：

然后：

反向表达式： 2-3-5

后缀：2 3 5---（像a^b^b到后缀：abc^^^，因为它也是右关联的）

反向--5 3 2

Answer 2

（b*b-4*a*c）/（2*c）方程——1<现在我将通过替换不同的变量，一次做两个项，从数学上解决这个问题
=

xi-2c*/
bb*yc*-2c*/

bb*4a*c*-2a*/

Answer 3

你的方法不正确，看看注释，它说（a b）c=a（b c）。（a b）*c呢？（a b）*c！=a（b*c）。根据你的手动算法，你把最后一个放在前面。这是不正确的。如果你用*而不是last，你把它放在哪里了？只要考虑到这一点，你就可以很容易地发现你的算法的问题。解决这个问题的另一个算法是在继续之前插入它。将每个左括号替换为其中的运算符。例如，（（1 (2*3)) ((5*6) (7/8)))然后变成1*23 *56 /78。如果内部运算符的优先级相同，则算法是正确的。如果不是，它就会失败。

注意：你的答案也可以通过括号的排列得到。（（（1 (2*3)) (5*6)) (7/8))然后变成1*23*56/78。但是如果最后一个是*而不是，那么它就不起作用了。