2 أنواع التعبيرات – بوستفيكس و اختصار. القواعد الرئيسية للتحويل.

This post is also available in: English (الإنجليزية)

ما هو التعبير الحسابي؟

التعبير الحسابي هو تركيبة صحيحة نحويًا من الأرقام والعوامل والأقواس والمتغيرات. على سبيل المثال ، 34 15 ، 45.78 – 21.89 31 ، -18/7 ، 2.43 ^ 4 ، 6.52 * (-3) كلها تعبيرات حسابية.

تذكر أن بناء الجملة يعني القواعد الخاصة بتجميع بيان تم تكوينه بشكل صحيح. التعبيرات الحسابية هي أجزاء من العبارات ، لذلك يجب أن تتبع قواعد بناء الجملة لتكون صحيحة.

2 أنواع التعبيرات – بوستفيكس و اختصار: قواعد تقييم التعبيرات

فيما يلي قواعد تقييم التعبير الحسابي:

• يتم تقييم التعبيرات دائمًا من اليسار إلى اليمين.
• إذا تمت مصادفة عامل في عملية التقييم ، تتم مقارنة أولويته بأولوية العامل التالي. إذا كانت القيمة التالية أقل ، فقم بتقييم عامل التشغيل الحالي بمعاملاته. على سبيل المثال في 2 * 7-8 ، تمت مصادفة عامل التشغيل * أولاً. نظرًا لأن “-” أقل ، يتم تقييم 2 * 7 أولاً بتحويل التعبير إلى 14-8. وبالتالي ، تكون النتيجة 6.
• إذا كان العامل التالي مساويًا للمشغل الحالي ، يتم استخدام قواعد الارتباط لتحديد العامل الذي يجب تقييمه أولاً. على سبيل المثال ، إذا كان كل من عامل التشغيل الحالي والتالي * ، فسيتم تقييم 2 * 3 * 4 على أنه (2 * 3) * 4. من ناحية أخرى ، إذا كان العامل هو ^ (رفع الطاقة) ، فسيتم تقييم 2 ^ 3 ^ 4 على أنه 2 ^ (3 ^ 4).
• إذا كان الرقم التالي أعلى من المشغل الحالي ، فيجب أن يستمر الفحص مع المشغل التالي. على سبيل المثال ، في 3 2 * 3 ^ 2 ، العامل الأول هو ، والعامل التالي * له أولوية أعلى ، يستمر الفحص *. بمجرد وصول الفحص إلى * ، نظرًا لأن العامل التالي ^ أعلى ، يتم تقييم 3 ^ 2 أولاً ، مما يؤدي إلى تحويل التعبير المعطى إلى 3 2 * 9. ثم يتم فحص التعبير الجديد مرة أخرى. العامل التالي الذي سيتم تقييمه هو * ، متبوعًا بـ. وهكذا يصبح التعبير 3+ 18 ، مما ينتج عنه في النهاية 21.

في كثير من الأحيان ، تحتوي هذه التعبيرات على أقواس – () (أقواس) أو {} (أقواس) أو [] (أقواس مربعة). في مثل هذه الحالات ، يتم تقييم الأقواس الداخلية أولاً ثم الأقواس الخارجية. أثناء تقييم تعبير داخل الأقواس ، يتم اتباع القواعد المذكورة أعلاه. على سبيل المثال في حالة [12 – {5 * (3 – 4)}] ، أولاً وقبل كل شيء ، يتم تقييم 3-4 داخل الأقواس (و). ينتج عن هذا [12 – {5 * (-1)}]. الآن يتم تقييم التعبير الموجود داخل {and} والذي ينتج عنه [12 – (-5)] والذي يساوي 12 5 = 17.

ما هي علامات أقحم و بوستفيكس و اختصار؟

تدوينات أقحم و بوستفيكس و اختصار هي ثلاث طرق مختلفة ولكن متكافئة لكتابة التعبيرات. من الأسهل توضيح الاختلافات من خلال النظر في أمثلة المشغلين الذين يأخذون عاملين. لنفكر في المعاملين X و Y مع عامل تشغيل واحد “”.

تدوين اللاحق: X Y

العوامل مكتوبة بين معاملاتهم. هذه هي الطريقة المعتادة لكتابة التعابير.

تدوين بوستفيكس (المعروف أيضًا باسم “التدوين البولندي العكسي”): X Y

يتم كتابة العوامل بعد معاملاتهم.

تدوين البادئة (المعروف أيضًا باسم “التدوين البولندي“): X Y

العوامل مكتوبة قبل معاملاتهم.

الآن ، دعنا نمدها لأكثر من معاملين وأكثر من عامل واحد. لنفكر في المعاملات A و B و C و D والمشغلات مثل “*” و “” و “/”.

تدوين أقحم

عادةً ما يُؤخذ تعبير مثل A * (B C) / D على أنه يعني شيئًا مثل: “أولاً ، أضف B و C معًا ، ثم اضرب النتيجة في A ، ثم اقسم على D لإعطاء الإجابة النهائية.”

يحتاج تدوين أقحم إلى معلومات إضافية لجعل ترتيب تقييم المشغلين واضحًا: القواعد المضمنة في اللغة حول أسبقية المشغل والترابط ، والأقواس () للسماح للمستخدمين بتجاوز هذه القواعد. على سبيل المثال ، تنص القواعد المعتادة للترابط على أننا نقوم بعمليات الضرب من اليسار إلى اليمين ، لذلك يُفترض أن الضرب في A يأتي قبل القسمة على D. وبالمثل ، تنص قواعد الأسبقية المعتادة على أننا نقوم بالضرب والقسمة قبل إجراء الجمع والطرح.

تدوين بوستفيكس

تعبير بوستفيكس الموضح أعلاه يعادل A B C * D /

يكون ترتيب تقييم العوامل دائمًا من اليسار إلى اليمين ، ولا يمكن استخدام الأقواس لتغيير هذا الترتيب. لأن “” على يسار “*” في المثال أعلاه ، يجب إجراء الإضافة قبل الضرب.

تعمل العوامل على القيم الموجودة على يسارها مباشرة. على سبيل المثال ، يستخدم “” أعلاه الحرفين “B” و “C”. يمكننا إضافة أقواس (غير ضرورية) لتوضيح ذلك: ((A (B C) *) D /)

وبالتالي ، فإن “*” تستخدم القيمتين التاليتين مباشرة: “A” ، ونتيجة الإضافة. وبالمثل ، فإن “/” تستخدم نتيجة الضرب و “D”.

نظرًا لأن عوامل بوستفيكس تستخدم القيم الموجودة على يسارها ، فسيتم بالفعل حساب أي قيم تتضمن عمليات حسابية أثناء انتقالنا من اليسار إلى اليمين ، وبالتالي لا يتم تعطيل ترتيب تقييم العوامل بالطريقة نفسها كما في تعبيرات البادئة.

تدوين البادئة

التعبيرات الواردة أعلاه تعادل / * A B C D.

بالنسبة إلى البادئة ، يتم تقييم العوامل من اليسار إلى اليمين وتكون الأقواس غير ضرورية. تعمل العوامل على أقرب قيمتين على اليمين. لقد أضفت أقواسًا (غير ضرورية) مرة أخرى لتوضيح ذلك: (/ (* A (B C) ) D)

على الرغم من أن “عوامل التشغيل البادئة يتم تقييمها من اليسار إلى اليمين” ، إلا أنها تستخدم قيمًا على يمينها ، وإذا كانت هذه القيم نفسها تتضمن حسابات ، فإن هذا يغير الترتيب الذي يجب تقييم العوامل فيه. في المثال أعلاه ، على الرغم من أن القسمة هي العامل الأول على اليسار ، إلا أنها تعمل على نتيجة الضرب ، وبالتالي فإن الضرب يجب أن يحدث قبل القسمة (وبالمثل يجب أن تحدث الإضافة قبل الضرب).

في جميع الإصدارات الثلاثة ، تحدث المعاملات بنفس الترتيب ، ويجب نقل العوامل فقط للحفاظ على المعنى صحيحًا. (هذا مهم بشكل خاص للمشغلين غير المتماثلين مثل الطرح والقسمة: A – B لا تعني نفس B – A ؛ الأولى تعادل A B – أو – A B ، والأخيرة B A – أو – B A).

أمثلة:

التحويل بين هذه الرموز

الطريقة الأكثر وضوحًا هي البدء بإدخال جميع الأقواس الضمنية التي توضح ترتيب التقييم ، على سبيل المثال:

يمكنك التحويل مباشرة بين هذه الأشكال الموضوعة بين قوسين ببساطة عن طريق تحريك عامل التشغيل داخل الأقواس ، على سبيل المثال (X + Y) أو (X Y +) أو (+ X Y). كرر هذا مع جميع العوامل في التعبير ، وأخيراً أزل أي أقواس زائدة.

الخطوات اللازمة لتحويل أقحم إلى بوستفيكس

1. ابحث في سلسلة أقحم من اليسار إلى اليمين.
2. تهيئة كومة شاغرة.
3. إذا كان الحرف الممسوح ضوئيًا هو مُعامل ، قم بإضافته إلى سلسلة بوستفيكس.
4. عندما يكون الحرف الممسوح ضوئيًا عاملًا وإذا كانت الحزمة فارغة ، ادفع الحرف إلى المكدس.
5. إذا كان الحرف الممسوح ضوئيًا عاملًا ولم تكن الحزمة فارغة ، فقم بمقارنة أسبقية الحرف بالعنصر الموجود أعلى المجموعة.
6. عندما يكون لأعلى المكدس أسبقية أعلى على الحرف الممسوح ضوئيًا ، انبثق المكدس الآخر ادفع الحرف الممسوح ضوئيًا إلى المكدس. كرر هذا الإجراء حتى لا يكون المكدس فارغًا ويكون لأعلى المكدس الأسبقية على الحرف.
7. كرر 4 و 5 خطوات حتى يتم مسح جميع الأحرف ضوئيًا.
8. بعد مسح جميع الأحرف ضوئيًا ، نضيف الحرف الذي قد يكون للمكدس إلى سلسلة بوستفيكس.
9. عندما لا يكون المكدس فارغًا ، أضف الجزء العلوي من المكدس إلى سلسلة بوستفيكس وانبثاق المكدس.
10. كرر العملية طالما أن المكدس ليس فارغًا.

تعبير Infix: (A / (B – C) * D E)

تعبير بوستفيكس المحول هو +ABC- / D * E

تحويل اللاحق إلى بوستفيكس باستخدام المكدس في ++C.

#define MAX 20
char stk[20];
// Push function here, inserts value in stack and increments stack top by 1
void push(char oper)
{
    if(top==MAX-1)
    {
        cout<<"stackfull!!!!";
    }
   
    else
    {
        top++;
        stk[top]=oper;
    }
}
// Function to remove an item from stack.  It decreases top by 1
char pop()
{
    char ch;
    if(top==-1)
    {
        cout<<"stackempty!!!!";
    }
    else
    {
        ch=stk[top];
        stk[top]='\0';
        top--;
        return(ch);
    }
    return 0;
}
int priority ( char alpha )
{
    if(alpha == '+' || alpha =='-')
    {
        return(1);
    }
 
    if(alpha == '*' || alpha =='/')
    {
        return(2);
    }
 
    if(alpha == '$')
    {
        return(3);
    }
 
    return 0;
}
string convert(string infix)
{
    int i=0;
    string postfix = "";   
    while(infix[i]!='\0')
    {       
        if(infix[i]>='a' && infix[i]<='z'|| infix[i]>='A'&& infix[i]<='Z')          
        {
            postfix.insert(postfix.end(),infix[i]);
            i++;
        }       
        else if(infix[i]=='(' || infix[i]=='{'  || infix[i]=='[')
        {
            push(infix[i]);
            i++;
        }        
        else if(infix[i]==')' || infix[i]=='}'  || infix[i]==']')
        {
            if(infix[i]==')')
            {
                while(stk[top]!='(')
                {               postfix.insert(postfix.end(),pop());
                }
                pop();
                i++;
            }
            if(infix[i]==']')
            {
                while(stk[top]!='[')
                {
                    postfix.insert(postfix.end(),pop());
                }
                pop();
                i++;
            }
 
            if(infix[i]=='}')
            {
                while(stk[top]!='{')
                {
                    postfix.insert(postfix.end(),pop());
                }
                pop();
                i++;
            }
        }
        else            
        {
            if(top==-1)
            {
                push(infix[i]);
                i++;
            }
 
            else if( priority(infix[i]) <= priority(stk[top])) {
                postfix.insert(postfix.end(),pop());
               
                while(priority(stk[top]) == priority(infix[i])){
                    postfix.insert(postfix.end(),pop());
                    if(top < 0) {
                        break;
                    }
                }
                push(infix[i]);
                i++;
            }
            else if(priority(infix[i]) > priority(stk[top])) {
                push(infix[i]);
                i++;
            }
        }
    }
    while(top!=-1)
    {
        postfix.insert(postfix.end(),pop());
    }
    cout<<"The converted postfix string is : "<<postfix; //it will print postfix conversion 
    return postfix;
}

int main()
{
    int cont;
    string infix, postfix;
    cout<<"\nEnter the infix expression : "; //enter the expression
    cin>>infix;
    postfix = convert(infix);
    return 0;
}

الخطوات اللازمة لتحويل أقحم إلى بادئة باستخدام المكدس

1. اعكس التعبير المعطى للواحة.
2. امسح الشخصيات واحدًا تلو الآخر.
3. إذا كان الحرف عبارة عن معامل ، فقم بنسخه إلى إخراج تدوين البادئة.
4. إذا كان الحرف عبارة عن قوس إغلاق ، فقم بدفعه إلى المكدس.
5. إذا كان الحرف عبارة عن قوس فتح ، فاضغط على العناصر الموجودة في المكدس حتى نجد قوس الإغلاق المقابل.
6. إذا كان أحد الرموز الممسوحة ضوئيًا هو عامل التشغيل وله أسبقية أكبر أو متساوية ، فقم بدفع المشغل إلى المجموعة.
7. إذا كان الحرف الذي تم مسحه ضوئيًا هو عامل التشغيل وله أسبقية أقل ، فقم بإخراج المشغل وإخراجه إلى إخراج تدوين البادئة ، ثم تحقق من الحالة أعلاه مع الجزء العلوي الجديد للمكدس مرة أخرى.
8. بعد مسح جميع الأحرف ، قم بعكس إخراج التدوين للبادئة.

تعبير Infix: (A / (B – C) * D E)

سلسلة Infix العكسية:) E D *) C – B (/ A (

عكس الناتج النهائي: * / A-BCDE

تعبير البادئة المحولة هو * / A-BCDE

إنفكس إلى بادئة التحويل باستخدام المكدس في C.

struct Stack *create (int max);
int stackFull (struct Stack *stack);
int stackEmpty (struct Stack *stack);
void pushElement (struct Stack *stack, int item);
int popElement (struct Stack *stack);
int peekElement (struct Stack *stack);
int checkOperand (char ch);
int precedence (char ch);
int postfix (char *expression);
void reverse (char *exp);
void brackets (char *exp);
void conversionInfixToPrefix (char *exp);
// A structure to represent a stack
struct Stack
{
  int top;
  int maxSize;
  int *array;
};
int main ()
{
  int n = 10;
  cout << "The infix expression is: \n";
  char expression[] = "(P+(Q*R)/(S-T))";
  cout << expression << "\n";
  conversionInfixToPrefix (expression);
  cout << "The prefix expression is: \n";
  cout << expression;
  return 0;
}
//stack implementation
struct Stack * create (int max)
{
  struct Stack *stack = (struct Stack *) malloc (sizeof (struct Stack));
  stack->maxSize = max;
  stack->top = -1;
  stack->array = (int *) malloc (stack->maxSize * sizeof (int));
  return stack;
}

// Checking with this function is stack is full or not
int stackFull (struct Stack *stack)
{
  if (stack->top == stack->maxSize - 1)
    {
      cout << "Will not be able to push maxSize reached\n";
    }
  // We know array index from 0 and maxSize starts from 1
  return stack->top == stack->maxSize - 1;
}

// if Stack is empty when top is equal to -1 and return true
int stackEmpty (struct Stack *stack)
{
  return stack->top == -1;
}

// Push function it inserts value in stack and increments stack top by 1
void pushElement (struct Stack *stack, int item)
{
  if (stackFull (stack))
    return;
  stack->array[++stack->top] = item;
}

// pop Function it remove an item from stack and decreases top by 1 
int popElement (struct Stack *stack)
{
  if (stackEmpty (stack))
    return INT_MIN;
  return stack->array[stack->top--];
}

// Function to return the top from stack without removing it 
int peekElement (struct Stack *stack)
{
  if (stackEmpty (stack))
    return INT_MIN;
  return stack->array[stack->top];
}

// A function check the given character is operand 
int checkOperand (char ch)
{
  return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}

// Fucntion to compare precedence if return larger value means higher precedence 
int precedence (char ch)
{
  switch (ch)
    {
    case '+':
    case '-':
      return 1;

    case '*':
    case '/':
      return 2;

    case '^':
      return 3;
    }
  return -1;
}

// The function for infix to postfix conversion 
int postfix (char *expression)
{
  int i, j;
  struct Stack *stack = create (strlen (expression));
  if (!stack)		
    return -1;

  for (i = 0, j = -1; expression[i]; ++i)
    {
     // checking the character we scanned is operand or not
      if (checkOperand (expression[i]))
	expression[++j] = expression[i];

      // if we scan character push it to the stack
      else if (expression[i] == '(')
	pushElement (stack, expression[i]);

      //if we scan character we need to pop and print from the stack  
      else if (expression[i] == ')')
	{
	  while (!stackEmpty (stack) && peekElement (stack) != '(')
	    expression[++j] = popElement (stack);
	  if (!stackEmpty (stack) && peekElement (stack) != '(')
	    return -1;		// invalid expression             
	  else
	    popElement (stack);
	}
      else			// if an operator
	{
	  while (!stackEmpty (stack)
		 && precedence (expression[i]) <=
		 precedence (peekElement (stack)))
	    expression[++j] = popElement (stack);
	  pushElement (stack, expression[i]);
	}

    }

  // if all first expression characters are scanned
 // adding all left elements from stack to expression
  while (!stackEmpty (stack))
    expression[++j] = popElement (stack);
    expression[++j] = '\0';
}

void reverse (char *exp)
{				//reverse function for expression

  int size = strlen (exp);
  int j = size, i = 0;
  char temp[size];

  temp[j--] = '\0';
  while (exp[i] != '\0')
    {
      temp[j] = exp[i];
      j--;
      i++;
    }
  strcpy (exp, temp);
}

void brackets (char *exp)
{
  int i = 0;
  while (exp[i] != '\0')
    {
      if (exp[i] == '(')
	exp[i] = ')';
      else if (exp[i] == ')')
	exp[i] = '(';
      i++;
    }
}

void conversionInfixToPrefix (char *exp)
{
  int size = strlen (exp);
  reverse (exp);
  brackets (exp);
  postfix (exp);
  reverse (exp);
}