การประเมินคำนำหน้าใน C++

ในบทความนี้ เราจะพูดถึง การประเมินคำนำหน้านิพจน์

คำนำหน้านิพจน์

ในสัญกรณ์นี้ โอเปอเรเตอร์คือนำหน้า ตัวถูกดำเนินการ เช่น ตัวถูกดำเนินการเขียนก่อนตัวถูกดำเนินการ ตัวอย่างเช่น +ab . ซึ่งเทียบเท่ากับสัญกรณ์ infix a + b . สัญกรณ์คำนำหน้าเรียกอีกอย่างว่า สัญกรณ์โปแลนด์ .

หากต้องการอ่านเพิ่มเติม

ตัวอย่าง:

* + 6 9 - 3 1

นิพจน์คำนำหน้าจะถูกประเมินเร็วกว่านิพจน์ infix นอกจากนี้ยังไม่มีวงเล็บในนิพจน์คำนำหน้าซึ่งทำให้ประเมินเร็วขึ้น

อัลกอริทึมในการประเมิน Prefix Expression:

การประเมินนิพจน์คำนำหน้าต้องใช้โครงสร้างข้อมูลแบบสแตก เราจะผลักตัวดำเนินการในสแต็กแล้วแก้นิพจน์

เราจะเยี่ยมชมแต่ละองค์ประกอบของนิพจน์ทีละรายการ หากองค์ประกอบปัจจุบันเป็นตัวถูกดำเนินการ เราจะผลักมันไปที่สแต็ก และหากเป็นโอเปอเรเตอร์ เราจะเปิดโอเปอเรเตอร์สองตัว ดำเนินการ ตัวถูกดำเนินการ ตัวถูกดำเนินการ แล้วผลักผลลัพธ์กลับไปยังสแต็ก

อัลกอริทึม −

ขั้นตอนที่ 1: เริ่มจากองค์ประกอบสุดท้ายของนิพจน์

ขั้นตอนที่ 2: ตรวจสอบองค์ประกอบปัจจุบัน

ขั้นตอนที่ 2.1: หากเป็นตัวถูกดำเนินการ ให้ดันไปที่สแต็ก
ขั้นตอนที่ 2.2: ถ้าเป็นโอเปอเรเตอร์ ให้ป๊อปสองตัวถูกดำเนินการจากสแต็ก ดำเนินการและดันองค์ประกอบกลับไปที่สแต็ก

ขั้นตอนที่ 3: ทำเช่นนี้จนกว่าองค์ประกอบทั้งหมดของนิพจน์จะถูกข้ามและกลับด้านบนของสแต็กซึ่งจะเป็นผลมาจากการดำเนินการ

มาดูการทำงานของอัลกอริทึมของเราเพื่อแก้นิพจน์คำนำหน้า

คำนำหน้านิพจน์ :

* + 6 9 - 3 1

ทำซ้ำ :1

สแกนองค์ประกอบแล้ว => 1

การทำงาน => กดไปที่ stack
กอง => 1

ทำซ้ำ :2

สแกนองค์ประกอบแล้ว => 3

การทำงาน => กดไปที่ stack
กอง => 3 , 1

ทำซ้ำ :3

สแกนองค์ประกอบ => -

Operation => ป๊อปสองจากสแต็ก ดำเนินการและดันผลลัพธ์กลับ

3 - 1 =2
กอง => 2

ทำซ้ำ :4

สแกนองค์ประกอบแล้ว => 9

การทำงาน => กดไปที่ stack
กอง => 9 , 2

วนซ้ำ :5

สแกนองค์ประกอบแล้ว => 6

การทำงาน => กดไปที่ stack
กอง => 6, 9 , 2

ทำซ้ำ :6

สแกนองค์ประกอบ => +

Operation => ป๊อปสองจากสแต็ก ดำเนินการและดันผลลัพธ์กลับ

6 + 9 =15

กอง => 15 , 2

ทำซ้ำ :7

สแกนองค์ประกอบแล้ว => *

Operation => ป๊อปสองจากสแต็ก ดำเนินการและดันผลลัพธ์กลับ

15 * 2 =30
กอง => 30

End => กลับด้านบนของ stack, ผลลัพธ์ =30.

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

double evaluatePrefix(string prefixExp) {
   
   stack<double> operendStack;
   int size = prefixExp.size() - 1;
   
   for (int i = size; i >= 0; i--) {

      if (isdigit(prefixExp[i]))
         operendStack.push(prefixExp[i] - '0');
      else {
         double o1 = operendStack.top();
         operendStack.pop();
         double o2 = operendStack.top();
         operendStack.pop();
         if( prefixExp[i] == '+')
            operendStack.push(o1 + o2);
         else if( prefixExp[i] == '-')
            operendStack.push(o1 - o2);
         else if( prefixExp[i] == '*')
            operendStack.push(o1 * o2);
         else if( prefixExp[i] == '/')
            operendStack.push(o1 / o2);
         else{
            cout<<"Invalid Expression";
            return -1;
         }
      }
   }
   return operendStack.top();
}

int main()
{
   string prefixExp = "*+69-31";
   cout<<"The result of evaluation of expression "<<prefixExp<<" is "<<evaluatePrefix(prefixExp);
   return 0;
}

ผลลัพธ์ -

The result of evaluation of expression *+69-31 is 30