Infix到后缀

Question

我试图将infix转换为postfix.For示例："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”，这是错误的，我多次修改了代码，但仍然看不到问题。如果有人能帮忙就太好了。

Answer 1

空间

您不会在后缀变量上放置任何空格。您只检查当前字符是否是“有趣”字符(数字、运算符)之一，而不是它是否是空格。因此，如果当前字符是空格，则只需跳过它，就不会将其复制到后缀。

因为您在后缀中只添加了您检查过的字符，所以您的结果是完全没有空格。

你可以这样解决：

• 添加一个名为inNumber的布尔值，首先将其设置为true。
• 无论何时处理一个数字，在将其添加到postfix之前，请检查inNumber是否为真。如果是的话，首先添加一个空格。
• 如果您刚刚处理了一个数字，请将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 for *和/中。当然，如果位于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()。
• 您没有进行任何语法检查。我不确定这是不是因为这是家庭作业，但在现实生活中，您应该检查每个(都有一个)匹配，每个操作符都有两个操作数，还应该处理开头可能有-的负数。

Answer 2

问题是，您没有添加空格。但是，您不能简单地在每个数字之间添加一个空格。您必须确保在整数的数字之间没有添加空格。为了解决这个问题，我只在if(infixExpr.charAt(i) == '+' || infixExpr.charAt(i) == '-')之后添加了一个if(infixExpr.charAt(i) == '+' || infixExpr.charAt(i) == '-')，在if(infixExpr.charAt(i) == '*' || infixExpr.charAt(i) == '/' )之后又添加了一个if(infixExpr.charAt(i) == '*' || infixExpr.charAt(i) == '/' )。这背后的逻辑是，一旦你遇到一个运算符，你就知道操作符之前的一切都是数字。现在，当我运行程序时，输出是20 2 3 *+2 8 *+5 4。在操作符之间仍然需要添加一些空格，但我将让您处理。

修改后的代码：

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

..。

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

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;
}