0

我需要将 array_name[i, i*k, ik] 之类的表达式转换为反向波兰表示法。我基本上在做的是尝试将这样的表达式翻译： if(array_name[i, j+k]>=a+b) array_name[i, j*k] = a+2; else x = a / b; 使用正则表达式转换为 RPN。我已经有一个非常丑陋的巨大正则表达式，它匹配：if, else, + - * / = == ( ) <= >= < > !=以及匹配此模式的所有单词：[a-zA-z][a-zA-z0-9_]*。而且我还有将中缀算术表达式转换为 RPN 的代码。这里是：

/// <summary>
/// Returns the collection of all the lexemes of the expression 
/// using Regex.
/// The Regex created works fine with 'if else' constructions and is good 
///with 
///any variable name possible in C#, with arithmetical expressions, 
///like +, -, /, and all the boolean operators.
/// </summary>
/// <param name="input">String expression in infix notation.</param>
/// <returns>Collection of all the lexemes of the expression</returns>
private static MatchCollection GetMatchCollection(string input)
{
    var rx =
        new Regex(
            @"/\bif\b|\belse\b|\(|\)|\+|\-|\*|\<=|\>=|\\|\>|\<|(?<![!=])[!=]=(?!=)|([a-zA-Z][a-zA-z0-9_]*)|(\d+\.?\d*)|(?<!=)=(?!=)|\/|/^/g");
    return rx.Matches(input);
}


/// <summary>
/// Translates the infix expression into RPN
/// </summary>
/// <param name="input">String expression in infix notation.</param>
/// <returns>RPN expression</returns>
public static string Translate(string input)
{
    var mc = GetMatchCollection(input);

    var id = new Regex(@"[a-zA-z][a-zA-z0-9_]*"); // regex for identifiers
    var num = new Regex(@"\d+\.?\d*"); // regex for decimals
    var skobki = new Regex(@"\(|\)"); // regex for braces
    object[] operators =
    {
        "(", ")", "else", "*", "/", "+", "-", "=", "<", ">", "<=", ">=", "==", "!=", "&&",
        "||", "if"
    }; // operators by priority

    var opers = new Regex(@"\(|\)|\+|\-|\*|\/|<=?|>=?|!=|=|&&|\|\|\bif\b|\belse\b"); // regex for operators

    var stOper = new Stack();
    var expr = new ArrayList();
    foreach (Match m in mc)
    {
        var m1 = id.Match(m.Value);
        if (m1.Success) { expr.Add(m1.Value); continue; }
        m1 = num.Match(m.Value);
        if (m1.Success) { expr.Add(m1.Value); continue; }
        m1 = skobki.Match(m.Value);
        if (m1.Success)
        {
            if (m1.Value == "(") { stOper.Push(m1.Value); continue; }
            var op = stOper.Pop().ToString();
            while (op != "(")
            {
                expr.Add(op);
                op = stOper.Pop().ToString();
            }
            continue;
        }
        m1 = opers.Match(m.Value);
        if (m1.Success)
        {
            try
            {
                while (Array.IndexOf(operators, m1.Value) > Array.IndexOf(operators, stOper.Peek()))
                {
                    if (stOper.Peek().ToString() == "(") break;
                    expr.Add(stOper.Pop().ToString());
                }
            }
            catch (Exception)
            {
                // stack is empty
            }
            stOper.Push(m1.Value);
        }
    }
    while (stOper.Count != 0)
    {
        expr.Add(stOper.Pop().ToString());
    }


    // Make the RPN expression string 
    // from the ArrayList expr.
    var res = new StringBuilder();
    foreach (var s in expr)
        res.Append(s).Append(' ');
    return res.ToString();
}

如何修改代码以使该方法public static string Translate(string input)将简单的表达式（如 array_name[i,k*i-1]）转换为 RPN 表达式？

请注意，该public static string Translate(string input)方法仅适用于简单的算术表达式，但不适用于我上面提供的那个（if-else 语句）。

4

2 回答 2

2

正则表达式不是要走的路。将其解析（可能利用一些解析器生成器）成抽象语法树并将其输出到 RPN，这很简单。

于 2015-02-12T15:07:15.980 回答
0

解决了这个问题。这是算法。 

class InfixToPostfixConverter
    {
        private readonly Stack<string> _stack;
        private readonly string[] _input;
        private readonly Dictionary<string, int> _priorities;
        private readonly List<string> _poliz;

        public InfixToPostfixConverter(string input)
        {
            _input = input.Split(new[] {' '}, StringSplitOptions.RemoveEmptyEntries);
            _stack = new Stack<string>();
            _poliz = new List<string>();

            _priorities = new Dictionary<string, int>
            {
                {"(", 0},
                {")", 0},
                {"[", 0},
                {"if", 0},
                {"flag", 0},
                {">", 1},
                {"<", 1},
                {"<=", 1},
                {">=", 1},
                {"=", 1},
                {"==", 1},
                {"!=", 1},
                {"+", 2},
                {"-", 2},
                {"*", 3},
                {"/", 3},
                {"^", 4},
                {"@", 5}
            };
        }

        public string Translate()
        {
            return ConvertInfixToPostfix();
        }

        private string ConvertInfixToPostfix()
        {
            int countAts = 0;

            bool reachedElse = false;

            foreach (var lexeme in _input)
            {

                if (lexeme.Equals("if"))
                {
                    _stack.Push(lexeme);
                    _stack.Push("flag");

                }

                else if (lexeme.Equals("else"))
                {
                    _poliz.Add("null");
                    _poliz.Add("1B");
                    reachedElse = true;
                    _poliz[_poliz.FindIndex(x => x.Equals("null"))] = _poliz.Count.ToString();

                }

                else if (Regex.IsMatch(lexeme, @"[a-zA-Z][a-zA-z0-9_]*|\d+\.?\d*")
                         && !lexeme.Equals("if") && !lexeme.Equals("else"))
                {
                    _poliz.Add(lexeme);

                }

                else if (lexeme.Equals(";"))
                {
                    if (!reachedElse)
                    {
                        while (_stack.Count != 0 && !_stack.Peek().Equals("if"))
                        {
                            _poliz.Add(_stack.Pop());
                        }


                        if (_stack.Count != 0)
                        {
                            _stack.Pop();
                        }
                    }
                    else
                    {
                        while (_stack.Count != 0)
                        {
                            _poliz.Add(_stack.Pop());
                        }
                        _poliz[_poliz.FindIndex(x => x.Equals("null"))] = _poliz.Count.ToString();
                    }
                }

                else if (lexeme.Equals(","))
                {
                    countAts++;
                    while (_stack.Count != 0 && !_stack.Peek().Equals("["))
                    {
                        _poliz.Add(_stack.Pop());
                    }
                }

                else if (lexeme.Equals(")") || lexeme.Equals("]"))
                {
                    var brace = lexeme.Equals(")") ? "(" : "[";

                    while (_stack.Count != 0 && !_stack.Peek().Equals(brace))
                    {
                        _poliz.Add(_stack.Pop());
                    }
                    _stack.Pop();

                    if (_stack.Peek().Equals("flag"))
                    {
                        _stack.Pop();
                        _poliz.Add((_poliz.Count + 3).ToString());
                        _poliz.Add("null");
                        _poliz.Add("3Y");
                    }

                    if (lexeme.Equals("]"))
                    {
                        countAts++;
                        _poliz.Add(countAts.ToString());
                        _poliz.Add(_stack.Pop());
                        countAts = 0;
                    }
                }

                else
                {
                    if (_stack.Count != 0 && !lexeme.Equals("(") && !lexeme.Equals("["))
                    {
                        for (;
                            _stack.Count != 0 &&
                            _priorities[lexeme] <= _priorities[_stack.Peek()];
                            _poliz.Add(_stack.Pop())) {}
                    }

                    if (lexeme.Equals("["))
                    {
                        countAts++;
                        _stack.Push("@");
                    }
                    _stack.Push(lexeme);
                }

            }


            return _poliz.Aggregate(string.Empty, (current, x) => current + (x + " "));
        }
    }
于 2015-02-15T09:47:47.253 回答