0

我正在制作一个转换器，它将接受中缀表达式并将它们转换为后缀表达式。

Example:
Infix: 2 * 3 - 10 / 4
Postfix: 2 3 * 10 4 / -

我有一个完全编码的方法，但它返回的后缀表达式是

2     3   *   1 0     4 / -

这样做有两个问题： 1. 主要问题是它们是 1 和 0 之间的一个空格，当它们应该在一起时（10）。2. 有很多多余的空格，输出应该和上面提供的例子一样。

我已经研究过从中缀到后缀的转换，但我无法确定如何进行比单个数字表达式转换更多的操作。

下面附上我的 postfixtoinfix 类，表达式变量以完美间距保存上例中指示的中缀。

import java.util.*;

public class InfixToPostfix
{
//Declare Instance Variables
private String expression;
private Stack<Character> stack = new Stack<Character>();

//Constructor
public InfixToPostfix(String infixExpression)
{
        expression = infixExpression;
}//End of constructor

//Translate's the expression to postfix
public String translate()
{
    //Declare Method Variables
    String input = "";
    String output = "";
    char character = ' ';
    char nextCharacter = ' ';

    for(int x = 0; x < expression.length(); x++)
    {
        character = expression.charAt(x);

        if(isOperator(character))
        {
            while(!stack.empty() && precedence(stack.peek())>= precedence(character))
                output += stack.pop() + " ";
            stack.push(character);
        }   
        else if(character == '(')
        {
            stack.push(character);
        }
        else if(character == ')')
        {
            while(!stack.peek().equals('('))
                output += stack.pop() + " ";
            stack.pop();
        }
        else
        {
            if(Character.isDigit(character) && (x + 1) < expression.length() && Character.isDigit(expression.charAt(x+1)))
            {
                output += character;
            }
            else if(Character.isDigit(character))
            {
                output += character + " ";
            }   
            else
            {
                output += character;
            }
        }
    }//End of for

    while(!stack.empty())
    {
        output += stack.pop() + " ";
    }

    return output;
}//End of translate method

//Check priority on characters
public static int precedence(char operator)
{
    if(operator == '+' || operator =='-')
        return 1;
    else if(operator == '*' || operator == '/')
        return 2;
    else
        return 0;
}//End of priority method

public boolean isOperator(char element)
{
    if(element == '*' || element == '-' || element == '/' || element == '+')
        return true;
    else
        return false;
}//End of isOperator method

}//End of class
4

3 回答 3

2

您的代码没有将“10”视为一个实体，而是将其视为两个单独的字符“1”和“0”。对于任何不是运算符或括号的事情，你所做output += character + " ";的都会给你你的1 0而不是你想要的10。

于 2012-05-11T20:50:56.990 回答
0

将任意算术表达式从其中缀（即算术表达式的常规形式）转换为后缀形式的问题并不像最初看起来那么简单。

算术表达式代表一种上下文无关的语言，可以使用下推自动化来识别。作为这种识别的结果，可以构造语法树或 AST（抽象语法树），它们将自下而上遍历以构造后缀形式。

一本没有太多理论的很好的实用书是Language Implementation Patterns，我强烈推荐。

于 2012-05-11T20:55:48.217 回答
0

就像@digitaljoel 所说，您将单个字符识别为词汇标记，而不是完整的单词作为标记。

您应该让解析器调用一个方法来从输入中读取下一个完整的标记，而不是读取单个字符然后决定它是什么标记（运算符或操作数）。然后可以将令牌作为字符串（包含一个或多个组成令牌的字符）或作为类对象（包含令牌的文本和某种 token_type 属性）返回。

否则，您的解析器仅限于处理单字符标记。

Another benefit of using a separate lexical analyzer to read tokens is that you can handle whitespace in the lexer instead of in the parser.

于 2012-05-11T21:29:05.370 回答