I need to covert expressions like array_name[i, i*k, i-k] into Reverse Polish Notation.
What I'm basically doing is trying to translate the expression like this:
if(array_name[i, j+k]>=a+b) array_name[i, j*k] = a+2; else x = a / b;
into the RPN using regular expressions.
I already have quite an ugly huge regular expression, which matches: if, else, + - * / = == ( ) <= >= < > != and all the words that match this pattern: [a-zA-z][a-zA-z0-9_]*. And also I have the code that translates infix arithmetical expressions into RPN. Here it is:
/// <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();
}
How can I modify the code to make the method public static string Translate(string input) translate simple expressions like array_name[i,k*i-1] into the RPN expression?
Note, that the public static string Translate(string input) method works fine only with simple arithmetical expressions, but not with the one I provided above (the if-else statement).
Solved the issue. Here is the algorithm.
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 + " "));
}
}