Преобразование из инфикса в постфикс (обратная польская запись) работает с круглыми скобками, но не без
Правила назначения:
- Должен иметь отдельный класс Operator и отдельный класс PostFix, содержащий метод преобразования.
- Оцените слева направо.
- Операторы помещаются в стек.
- Только бинарные операторы
- Отдельный класс Operator и класс PostFix, где PostFix содержит метод Conversion.
- C#
Моя проблема:
Мое преобразование работает, если все / большая часть уравнения в скобках. Он работает без скобок, только если ввод в порядке операций.
Я считаю, что просто не проверяю приоритет должным образом, но я не уверен, что это проблема. Я переписывал свой метод преобразования 4 раза и потратил около 25 часов на настройку и прогон отладчика на разных итерациях метода и Google, но я просто не понимаю, в чем проблема в моем коде. Я вижу это во время отладки, но я не уверен, что мне нужно сделать, чтобы это исправить, поэтому я подумал, что, возможно, точка зрения третьей стороны поможет.
Примеры
Неверный вывод:
a=5+3/4-(9*8-1)*1 => a 5 3 + 4 / 9 8 * 1 - - 1 * =
should be a 5 3 4 / + 9 8 * 1 - - 1 * =
alpha = beta + gamma * delta => alpha beta gamma + delta * =
should be alpha beta gamma delta * + =
Правильный вывод:
a = ((((a+b)-c)*d)/(e+1)) => a a b + c - d * e 1 + / =
alpha = beta * gamma + delta => beta gamma * delta + alpha =
Мой код
Класс оператора:
class Operator
{
private byte precedence = 1; //Precedence of operator over others
private char identity = 'x'; //the character behind the operator
/// <summary>
/// Creates an operator based on the passed character
/// </summary>
/// <param name="OperatorIn">Character definition of the operator</param>
public Operator(char OperatorIn)
{
identity = OperatorIn;
switch (OperatorIn)
{
case '*':
precedence = 2;
break;
case '/':
precedence = 2;
break;
case '(':
precedence = 3;
break;
case ')':
precedence = 3;
break;
case '=':
precedence = 3;
break;
case '+':
precedence = 1;
break;
case '-':
precedence = 1;
break;
default:
precedence = 0;
break;
}//switch
}//Operator(char)
/// <summary>
/// Retrieves the char representation of the operator
/// </summary>
/// <returns>Char representation of the operator</returns>
public char ToChar()
{
return this.identity;
}//ToChar()
/// <summary>
/// Returns the byte value of precedence of the operator
/// </summary>
/// <returns>byte value of precedence</returns>
public byte GetPrecedence()
{
return this.precedence;
}
}//Operator
Метод конвертации:
public static string Convert(string infix)
{
#region original
Stack<Operator> OpStack = new Stack<Operator>();
String Postfix = String.Empty;
InfixPostfix.Operator Previous = new Operator('x'),
Current = null; //NextOp = new Operator(infix[infix.IndexOfAny(Ops, i)]);
char[] Ops = {'+','-','=','*','/'};
string term = String.Empty;
foreach(char c in infix)
{
if (Ops.Contains(c)) //if the char is one of the operator chars
{
Postfix += term + " "; //split term and add to output
while (OpStack.Count > 0) //While there's actually operators in the stack
{
Current = OpStack.Pop(); //Assign the operator as Current Operator
if (Current.GetPrecedence() < Previous.GetPrecedence()) //If Current Op is less priority than preceding Op
Postfix += Current.ToChar() + " "; //Output the character of the Op
else //If Current Op priority is higher than the previous
{
Previous = Current; //Store the current as previous to move on
OpStack.Push(Current); //Store current in stack
break; //Move to next char
}//else
}//while
OpStack.Push(new Operator(c)); //If stack is empty, push the operator
term = ""; // and reset the term to empty
}//if
else if (c == ')') //If the char is a close paren
{
Postfix += term + " "; //store the previous characters as a term in postfix
term = ""; //establish a new term
Previous = Current; //Set Current as the old Op
Current = OpStack.Pop(); //Get the new Current op
while (Current.ToChar() != '(') //Pop the stack until you get an open paren op
{
Postfix += Current.ToChar() + " "; //Add the term to the output string
//Previous = Current;
try
{
Current = OpStack.Pop(); //Try to pop another operator
}//try
catch(Exception) //If the stack is empty
{
return "Error! Mismatched parentheses!"; //Then there is a missing/misaligned paren
}//catch
}//while
}//else if
else if (c == '(') //If the op is an open paren
OpStack.Push(new Operator(c)); //store it
else if (c != ' ') //If it's an alphanumeric char,
term += c; //build a term with it
}//foreach
Postfix += term + " "; //add the last term to the output
while(OpStack.Count > 0) //If there are remaining ops on the stack,
{
Current = OpStack.Pop(); //pop them off
if (Current.ToChar() == '(' || Current.ToChar() == ')') //If there is a paren remaining
return "Error! Mismatched parentheses!"; // it's because of missing complement or misalignment
Postfix += Current.ToChar() + " "; //if regular op, add to output
}//while
return Postfix;
}
Заранее спасибо!
1 ответ
Итак, я получил несколько голосов, которые указали, что был интерес к ответу. Мое решение было снова разрушить то, что у меня было, и начать все сначала. Я несколько раз садился и просматривал алгоритм на бумаге, а затем проходил его при отладке по одной строке за раз. Это привело к некоторым "интересным" изменениям, чтобы закончить это.
Честно говоря, то, что я придумал, отвратительно - в какой-то момент у меня есть "если-еще, если-если-пока-если". Так что эта штука не красивая и, вероятно, действительно неэффективная. К счастью, я не оцениваю эффективность в этом классе, хаха. Мне просто нужно было сделать это, так как он должен быть в пятницу, и у меня есть проект Ассамблеи, чтобы начать. Тем не мение...
Код
Класс оператора обновил значения приоритета в конструкторе.
public Operator(char OperatorIn)
{
identity = OperatorIn;
switch (OperatorIn)
{
case '*':
precedence = 2;
break;
case '/':
precedence = 2;
break;
case '=':
precedence = 1;
break;
case '+':
precedence = 1;
break;
case '-':
precedence = 1;
break;
default:
precedence = 0;
break;
}//switch
}//Operator(char)
Структура аналогична для метода Convert. Там много if(Stack.Count>0) проверки, которые, вероятно, указывают на плохую логику внутри циклов и другие if/whiles. Но, похоже, работает отлично.
public static string Convert(string infix)
{
Stack<Operator> OpStack = new Stack<Operator>();
String Postfix = String.Empty;
Operator Previous = new Operator('x'),
Current = null;
char[] Ops = { '+', '-', '=', '*', '/' };
string term = String.Empty;
foreach (char c in infix) //Iterate through char at a time
{
if (c == '(') //If open paren
OpStack.Push(new Operator(c)); // put on the stack
else if (c == ')') //If close paren
{
Postfix += term + " "; //Output the term
term = ""; // and clear out the term holder
Previous = OpStack.Peek(); //Get a value to know Previous has as real value instead of 'x'
while (Previous.ToChar() != '(') // pop until we reach the open paren
{
if (OpStack.Count > 0)
Current = OpStack.Pop(); //Current becomes what was on top of the stack
if(Current.ToChar() != ')' && Current.ToChar() != '(')
Postfix += Current.ToChar() + " "; // add to output
try //Make sure we have more to pop
{
Previous = OpStack.Pop(); //Previous becomes what was 2nd on the stack
}//try
catch (Exception) //If there's nothing to pop and we're still in this loop
{
return "Error! Mismatched parentheses!"; //Mismatched or missing parenthesis
}//catch
}//while
}//else if
else if (Ops.Contains(c)) //If it's an operator
{
Postfix += term + " "; //output the term
term = ""; // and clear the term holder
Current = new Operator(c); //Assign the current character as Current Op
if (OpStack.Count > 0) //If there are previous ops in stack
{
Previous = OpStack.Peek(); // get top op on stack to compare
if (Previous.GetPrecedence() > Current.GetPrecedence() && OpStack.Count > 0) //Decide between > and =
{
while (Previous.GetPrecedence() > Current.GetPrecedence() && OpStack.Count > 0) //Pop until we find lesser precedence op
{
Previous = OpStack.Pop(); //Remove the compared value from stack
Postfix += Previous.ToChar() + " "; //Add the popped ops to output
if (OpStack.Count > 0) //make sure we aren't looping too far
Previous = OpStack.Peek(); //assign new value before compare occurs
}//while
}//if
else if(Previous.GetPrecedence() == Current.GetPrecedence() && OpStack.Count > 0 && Previous.ToChar() != '=') //Decide between > and =
{
while (Previous.GetPrecedence() == Current.GetPrecedence() && OpStack.Count > 0 && Previous.ToChar() != '=') //Pop until = precedence found
{
Previous = OpStack.Pop(); //Remove the compared value from stack
Postfix += Previous.ToChar() + " "; //Add the popped ops to output
if (OpStack.Count > 0) //make sure we aren't looping too far
Previous = OpStack.Peek(); //assign new value before compare occurs
}//while
}//else if
OpStack.Push(Current); //Once a <= op is found, store the Current op
continue;
}//if
else //If there are no ops on stack
OpStack.Push(Current); // store it immediately
}//else if
else if (c != ' ') //If alphanumeric
term += c; // add into term holder
}//foreach
Postfix += term + " "; //There will be a term left over after the final c, so output it
while(OpStack.Count > 0) //There may also be ops left, so pop them
{
Current = OpStack.Pop();
if (Current.ToChar() == '(' || Current.ToChar() == ')') //If there is a paren remaining
return "Error! Mismatched parentheses!"; // it's because of missing complement or misalignment
Postfix += Current.ToChar() + " "; //output the operator
}//while
return Postfix;
}//Convert v2