中缀表达式转后缀表达式

Question

我正在尝试将中缀表达式转换为后缀表达式。例如： "20 + 2 * 3 + (2*8 + 5)* 4" ->20 2 3 * + 2 8 * 5 + 4 * + 这是我的代码：

Stack<Character> s = new Stack<Character>();
String postfix = "";
boolean enter = true;
String infixExpr = "20 + 2 * 3     + (2*8 + 5)* 4";

for(int i = 0;i<infixExpr.length();i++){

    if(Character.isDigit(infixExpr.charAt(i)) == true){
        postfix = postfix + infixExpr.charAt(i);
    }
    if(infixExpr.charAt(i) == '+' || infixExpr.charAt(i) == '-'){
        if(s.isEmpty() == true){
            s.push(infixExpr.charAt(i));
        }
        else{
            if(s.peek() == '*' || s.peek() == '/' || s.peek() == '+' || s.peek() == '-'){
                while(s.isEmpty()== false){
                    postfix = postfix + s.pop();
                }
                s.push(infixExpr.charAt(i));
            }
            else{
                s.push(infixExpr.charAt(i));
            }
        }
    }
    if(infixExpr.charAt(i) == '*' || infixExpr.charAt(i) == '/' ){
        if(s.isEmpty() == true){
            s.push(infixExpr.charAt(i));
        }
        else{
            if(s.peek()== '+' || s.peek() == '-' || s.peek() == '('){
                s.push(infixExpr.charAt(i));
            }
            else if(s.peek() == '*' || s.peek() == '/'){
                while(s.isEmpty()== false){
                    postfix = postfix + s.pop();
                }
                s.push(infixExpr.charAt(i));
            }
        }
        if(infixExpr.charAt(i) == '('){
            s.push(infixExpr.charAt(i));
        }
        if(infixExpr.charAt(i) == ')'){
            while(enter){

                if(s.peek() == '('){
                    enter = false;
                }
                else{
                    postfix = postfix + s.pop();
                }
            }
        }
    }
}

如题所述，我应该得到“20 2 3 * + 2 8 * 5 + 4 * +”，但我得到了“2023*+28*+54”，这是错误的。我已经多次检查代码，但仍然找不到问题。如果有人能帮忙解决，那就太好了。

- Yunus Emre Güler

---

http://en.wikipedia.org/wiki/Shunting-yard_algorithm - Alexis King

你尝试使用调试器逐步执行代码了吗？ - Dawood ibn Kareem

Answer 1

空格

你的后缀变量中没有加入任何空格。你只检查当前字符是否为“有趣”的字符（数字、运算符），但并未检查它是否为空格。因此，如果当前字符是空格，你只是跳过它，不将其复制到后缀中。

由于你只在后缀中放置了经过检查的字符，所以最终没有任何空格。

你可以这样解决：

• 添加一个布尔变量称为inNumber，一开始将其设置为true。
• 每当处理数字时，在将其添加到postfix之前，检查inNumber是否为true。如果是，则先添加一个空格。
• 如果你刚刚处理完一个数字，请将inNumber设置为true。
• 如果你正在处理运算符，请将inNumber设置为false。
• 每当向堆栈中添加任何运算符时，请先添加一个空格。

inNumber的想法是属于同一数字的数字之间不应该有空格。但是，如果在我们在上一轮中处理运算符之后将数字添加到postfix中，则它属于新数字，因此应该在那里添加一个空格。

因此，基本上，你的数字处理代码应该如下所示：

        if(Character.isDigit(infixExpr.charAt(i)) == true){
            if ( ! inNumber ) {
                postfix += " ";
            }
            postfix = postfix + infixExpr.charAt(i);
            inNumber = true;
        }

在每个表明运算符的 if 语句中，您都应该设置 inNumber = false。

同时，每个将运算符添加到后缀表达式的位置应该像这样：

        postfix = postfix + " " + s.pop();

处理括号

你的另一个问题是如何处理()。

首先，你把检查(和)的代码放在了*和/的if里面。当然，如果在 i 位置的字符是*或/，那么它既不是(也不是)，所以这段代码永远不会被调用。

因此，你应该将括号的if移到外面，与检查数字和运算符的if处于同一级别。

此外，你对enter的使用是错误的。如果你有括号内的括号，比如( 3 + ( 5 + 7 ) )，那么在第一个)处，你会回到5后面的括号，这是可以的。但是，然后enter就变成了false，你就不能正确地处理外部的一对括号了。这对于(3 + 5 ) * ( 7 + 2 )也是正确的，因为你在程序开始后没有再次将enter设置为true。

你应该弹出堆栈上的内容并检查它是否是(，而不是使用enter：

        if(infixExpr.charAt(i) == '('){
            inNumber = false;
            s.push(infixExpr.charAt(i));
        }
        if(infixExpr.charAt(i) == ')'){
            inNumber = false;
            char popped;
            while ( ( popped = s.pop() ) != '(' ) {
                    postfix = postfix + " " + popped;
            }
        }        

---

未弹出的运算符

最后，在扫描输入完成后，您仍然会有等待在堆栈中的运算符！您必须将它们全部弹出并添加到postfix中。因此，在循环之后，您应该有：

    while ( ! s.isEmpty()) {
        postfix += " " + s.pop();
    }

---

附加说明：

• 如果用所有这些if语句代替，使用switch语句会更好、更清晰。
• 将布尔表达式与true进行比较没有意义。编写if (s.isEmpty() == true)的正确方式是if (s.isEmpty())，而不是s.isEmpty() != true，请使用!s.isEmpty()。
• 你没有做任何语法检查。我不确定是否因为这是家庭作业，但在现实生活中，你应该检查每个(是否与一个)匹配，每个运算符都有两个操作数，并处理可能以-开头的负数。

- RealSkeptic

Answer 2

问题是你没有添加空格。 但是，你不能简单地在每个数字之间添加一个空格。 你必须确保不会在整数的数字之间添加空格。 为了解决这个问题，我在if(infixExpr.charAt(i) == '+' || infixExpr.charAt(i) == '-')之后和if(infixExpr.charAt(i) == '*' || infixExpr.charAt(i) == '/' )之后分别添加了postfix += " ";。 这样做的逻辑是一旦遇到运算符，你就知道运算符之前的所有内容都是数字。 现在当我运行程序时，输出是20 2 3 *+2 8 *+5 4。 在运算符之间仍然需要添加几个空格，但这就交给你了。

修改后的代码：

    if(infixExpr.charAt(i) == '+' || infixExpr.charAt(i) == '-'){
        postfix += " ";

...

    if(infixExpr.charAt(i) == '*' || infixExpr.charAt(i) == '/' ){
        postfix += " ";

- nLee

Answer 3

这是我为你的答案编写的代码

#include<stack>
#include<iostream>
using namespace std;
bool high(char a,char b)
{
  if(b==' ')
    return true;
  else if(a==b)
    return false;
  else if(a=='/')
    return true;
  else if(a=='*'&&b!='/')
    return true;
  else if(b=='/')
    return false;
  else if(a!='/'&&b=='*')
    return false;
  else if(b=='-')
    return true;
  else if(a=='-'&&b!='(')
    return false;
  else if(b=='(')
    return true;
  else if(a=='(')
    return true;
  else if(a==')')
    return false;
}
main()
{
int k=0;
string s;
stack<char>s1;
s1.push(' ');
char ch;
while(cin>>ch)
{
    if(ch=='(')
    {
    k=1;
    s1.push(ch);}
    else if(ch>47&&ch<58)
    s.push_back(ch);
    else if(high(ch,s1.top()))
    s1.push(ch);
    else if(!high(ch,s1.top())&&ch!=')')
    {
        while(!s1.empty()&&!high(ch,s1.top()))
        {
            s.push_back(s1.top());
            s1.pop();
        }   
    s1.push(ch);}
    else if(ch==')')
    {
        while(!s1.empty()&&s1.top()!='(')
        {
            s.push_back(s1.top());
            s1.pop();
        }
        s1.pop();
        k=0;
    }

}
while(!s1.empty())
{
    s.push_back(s1.top());s1.pop();
}
cout<<s;
}

- bhavneet singh

---

为了帮助 OP 解决当前的问题，可以在回答中添加一些解释说明。 - ρяσѕρєя K

除非它解决了他的问题，否则它不是一个答案，如果它确实解决了问题，你需要说明原因。 - user207421