PDA

View Full Version : آموزش: تبدیل عبارت میانوندی به پسوندی و محاسبه آن Infix To Postfix and Compute Postfix



Mahmoud.Afrad
چهارشنبه 01 آذر 1391, 04:33 صبح
با سلام

در این تاپیک کد تبدیل Infix به Postfix و همچنین دریافت اعداد و محاسبه عبارت Postfix را قرار میدم.

کلاس آیتم را برای ذخیره هر جزء از عبارت Postfix به صورت زیر تعریف میکنیم:
enum types { Number, Variable, Operator };
class item
{
public string name;
public double value;
public types type;
}
name برای ذخیره نام متغیر درون رشته Infix هست. از value برای ذخیره مقدار یک متغیر و یا عدد استفاده شده و از type برای تعیین نوع آن جزء که عدد است یا متغیر و یا عملگر استفاده می شود.

تبدیل Infix به Postfix :
نحوه کار به این صورت هست که یک رشته Infix از کاربر دریافت میشه و از چپ به راست پیمایش شده و هر عملوند(شامل اعداد و نام متغیرها) در لیست آیتم های Postfix قرار می گیرد. عملگرها(شامل +-*/^) به پشته push می شوند. پرانتز باز "(" نادیده گرفته میشه و البته با روبرو شدن با پرانتز بسته ")" یک عملگر از پشته pop شده و به لیست postfix اضافه میشه. در انتهای پیمایش رشته infix ، عملگرهای باقیمانده در پشته را به لیست اضافه میکنیم.
برای تعیین اعداد ، نام متغیر و همچنین عملگرها به اینصورت عمل شده که از چپ به راست تا رسیدن به کاراکتری که از نوع عملگر باشد پیش رفته و وقتی به عملگر و یا به انتهای رشته رسیدیم مقادیر قبلی(temp) را برای تعیین اینکه عدد هست یا نه از طریق متد Pars سعی در تبدیل به double میکنیم. اگر خطایی رخ نداد و تبدیل انجام شد نوع آیتم را از نوع Number و در غیر اینصورت از نوع Variable و همچنین برای عملگرها نوع Operator را در نظر میگیرم.
آیتمهایی که از نوع عدد هستند value آنها عدد شده همان name است.

برای نمایش رشته postfix ، کافیست لیست را از ابتدا به انتها به رشته postfix اضافه کنیم.

در رشته Infix اگر تعداد پرانتزهای باز و بسته برابر نباشد و یا عملگری که نیاز به دو عملوند دارد دارای یک عملوند باشد رشته ورودی Infix نیست و نمی توان آنرا به Postfix تبدیل کرد.


محاسبه عبارت Postfix :
برای محاسبه رشته postfix ، ابتدا برای آیتمهایی که از نوع Variable هستند مقدار عددی را از کاربر دریافت کرده و در value آیتم متناظر قرار داده و نوع این آیتم را از Variable به Number تغییر می دهیم.(یعنی عدد متناظر هر متغیر را از کاربر دریافت می کنیم).
برای محاسبه عددی رشته postfix از چپ به راست جلو رفته و عملوندها(اعداد) را در پشته عملوندها(stackOperands) قرار می دهیم(push می کنیم) و با رسیدن به عملگر(+-*/^) ، با توجه به اینکه این عملگر چند عملوند نیاز دارد به همان تعداد از پشته pop کرده و عملگر را روی عملگرها(اعداد) اعمال کرده و نتیجه را در پشته push می کنیم. (البته باید در نظر داشت که عملوندی که ابتدا pop میشود عملوند دوم(op2) است و عملوندی که دوم pop میشود عملوند اول(op1) است. این به خاطر این است که ترتیب خروج از پشته عکس ترتیب قرار گیری در پشته است).
این روند را ادامه داده تا به انتهای عبارت postfix برسیم. در اینصورت پشته باید یک عنصر داشته باشد که همان جواب است و اگر بیش از یک عنصر داشته باشد عبارت postfix نبوده است.


کد کلاس:

using System;
using System.Collections.Generic;
using System.Text.RegularExpressions;

class InfixToPostfix
{
enum Types
{
Number,
Variable,
Operator
}

class Item
{
public string Name;
public double Value;
public Types Type;
}

// used for store postfix items
private List<Item> _listPostfixItems = new List<Item>();
// allowable operators
private string _operators = "+-*/()^";
private string _infix;
private string _postfix;


public string Infix
{
get { return _infix; }
set
{
_infix = value;
_postfix = ConvertToPostFix();
}
}

public string Postfix
{
get { return _postfix; }
}


public InfixToPostfix()
{

}

public InfixToPostfix(string infix)
{
Infix = infix;
}


public string GetPostfix()
{
if (string.IsNullOrEmpty(Infix))
{
throw new ArgumentNullException(nameof(Infix));
}

if (!IsValid(Infix))
{
throw new FormatException("The input is not currect Infix phrase");
}

_postfix = ConvertToPostFix();

return _postfix;
}

public double ComputeInfix()
{
if (string.IsNullOrEmpty(Infix))
{
throw new ArgumentNullException(nameof(Infix));
}

if (IsValid(Infix))
{
throw new FormatException("The input is not currect Infix phrase");
}

return Compute();
}


private string ConvertToPostFix()
{
char arrival;
Stack<char> oprerator = new Stack<char>(); //Creates a new Stack
string temp = string.Empty;

//Iterates characters in inFix
for (int i = 0; i < _infix.Length; i++)
{
char c = _infix[i];
if (char.IsNumber(c))
{
temp += c;
}
else
{
AddItemToList(ref temp);

if (c == '(')
{
oprerator.Push(c);
}
else if (c == ')') //Removes all previous elements from Stack and puts them in front of PostFix.
{
arrival = oprerator.Pop();
while (arrival != '(')
{
temp += arrival;
arrival = oprerator.Pop();
AddItemToList(ref temp);
}
}
else
{
if (oprerator.Count != 0 && Predecessor(oprerator.Peek(), c)) //If find an operator
{
arrival = oprerator.Pop();
while (Predecessor(arrival, c))
{
temp += arrival;
AddItemToList(ref temp);
if (oprerator.Count == 0)
{
break;
}
arrival = oprerator.Pop();
}
oprerator.Push(c);
}
else
{
oprerator.Push(c); //If Stack is empty or the operator has precedence
}
}
}
}

AddItemToList(ref temp);

while (oprerator.Count > 0)
{
arrival = oprerator.Pop();
temp += arrival;
AddItemToList(ref temp);
}

foreach (Item item in _listPostfixItems)
{
_postfix += item.Name;
}

return _postfix;
}

private bool Predecessor(char firstOperator, char secondOperator)
{
Dictionary<char, ushort> precedence = new Dictionary<char, ushort>()
{
{'(', 1},
{'+', 2},
{'-', 2},
{'*', 3},
{'/', 3},
{'%', 3}
};
return precedence[firstOperator] >= precedence[secondOperator];
}

private double Compute()
{
// used for postfix computation
Stack<double> stackOperands = new Stack<double>();
double result = 0;
//// Get Value for all variable items
//for (int k = 0; k < _listPostfixItems.Count; k++)
//{
// if (_listPostfixItems[k].Type == Types.Variable)
// {
// Console.Write("Enter " + _listPostfixItems[k].Name + " : ");
// string v = Console.ReadLine();
// try
// {
// _listPostfixItems[k].Value = double.Parse(v);
// _listPostfixItems[k].Type = Types.Number;
// }
// catch (Exception ex)
// {
// Console.WriteLine(ex.Message);
// k--;
// }
// }
//}

for (int p = 0; p < _listPostfixItems.Count; p++) // compute _postfix
{
if (_listPostfixItems[p].Type == Types.Number)
{
stackOperands.Push(_listPostfixItems[p].Value);
}
else
{
if (stackOperands.Count >= 2)
{
double op2 = stackOperands.Pop();
double op1 = stackOperands.Pop();

// Do operation
if (_listPostfixItems[p].Name == "^")
{
stackOperands.Push(Math.Pow(op1, op2));
}
else if (_listPostfixItems[p].Name == "*")
{
stackOperands.Push(op1*op2);
}
else if (_listPostfixItems[p].Name == "/")
{
stackOperands.Push(op1/op2);
}
else if (_listPostfixItems[p].Name == "+")
{
stackOperands.Push(op1 + op2);
}
else if (_listPostfixItems[p].Name == "-")
{
stackOperands.Push(op1 - op2);
}
}
else if (stackOperands.Count == 1 && _listPostfixItems[p].Name == "-")
{
double op = stackOperands.Pop();
stackOperands.Push(op*(-1));
}
}
}

if (stackOperands.Count == 1)
{
result = stackOperands.Pop();
}

return result;
}

private void AddItemToList(ref string name)
{
if (name == string.Empty) return;
Item n = new Item();
try
{
n.Value = double.Parse(name);
n.Name = "{" + name + "}";
n.Type = Types.Number;
}
catch
{
n.Name = name;
if (_operators.Contains(n.Name))
{
n.Type = Types.Operator;
}
else
{
n.Type = Types.Variable;
}
}
_listPostfixItems.Add(n);
name = string.Empty;
}

private bool IsValid(string input)
{
Regex operators = new Regex(@"[\-+*/%]", RegexOptions.IgnorePatternWhitespace | RegexOptions.Compiled);
if (string.IsNullOrEmpty(input))
{
return (false);
}


int countOfOpenParentheses = 0, countOfCloseParentheses = 0;


foreach (char c in input)
{
if (c == '(')
{
countOfOpenParentheses++;
}
else if (c == ')')
{
countOfCloseParentheses++;
}
}

if (countOfOpenParentheses != countOfCloseParentheses)
{
return false;
}

string tempString = operators.Replace(input, ".");

if (tempString.EndsWith("."))
{
return false;
}

string[] contains = new string[] {"(.)", "()", "..", ".)"};

foreach (string s in contains)
{
if (tempString.Contains(s))
{
return false;
}
}

operators = new Regex(@"[().]", RegexOptions.IgnorePatternWhitespace | RegexOptions.Compiled);
tempString = operators.Replace(tempString, string.Empty);

foreach (char c in tempString)
{
if (!char.IsNumber(c))
{
return false;
}
}

if (input.Contains("."))
{
return false;
}

tempString = input;

operators = new Regex(@"[1234567890]", RegexOptions.IgnorePatternWhitespace | RegexOptions.Compiled);
tempString = operators.Replace(tempString, ".");

if (tempString.Contains(".."))
{
return false;
}
if (input.StartsWith("*") || input.StartsWith("/") || input.StartsWith("%")
|| input.StartsWith("+") || input.StartsWith("-"))
{
return false;
}

contains = new string[] {"(%", "(/", "(*", "*", "(+", "(-"};
foreach (string s in contains)
{
if (input.Contains(s))
{
return false;
}
}

int begin = 0, end = 0;
foreach (char c in input)
{
if (c == '(')
{
begin++;
}
if (c == ')')
{
end++;
}
if (end > begin)
{
return false;
}
}
return true;
}
}

با کمک از http://www.codeproject.com/Tips/370486/Converting-InFix-to-PostFix-using-Csharp-VB-NET
توضیح الگوریتم در http://open-mind.ir/1394/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85-%D8%AA%D8%A8%D8%AF%DB%8C%D9%84-infix-%DB%8C%DA%A9-%D8%B9%D8%A8%D8%A7%D8%B1%D8%AA-%D9%85%D8%AD%D8%A7%D8%B3%D8%A8%D8%A7%DB%8C%DB%8C-%D8%A8%D9%87-postfix