ประเมิน Reverse Polish Notation ในโปรแกรม C ++

สมมุติว่าเรามี Reverse polish notation และเราต้องประเมินค่า สัญกรณ์โปแลนด์ย้อนกลับเรียกอีกอย่างว่านิพจน์ postfix ที่นี่เราต้องใช้โครงสร้างข้อมูลสแต็กเพื่อแก้นิพจน์ postfix

จากนิพจน์ postfix เมื่อพบตัวถูกดำเนินการบางตัว ให้พุชพวกมันในสแต็ก เมื่อพบโอเปอเรเตอร์บางตัว รายการสองรายการจะถูกดึงออกจากสแต็ก จากนั้นจึงดำเนินการตามลำดับที่ถูกต้อง หลังจากนั้น ผลลัพธ์ก็จะถูกผลักเข้าไปในสแตกเพื่อใช้ในอนาคต หลังจากเสร็จสิ้นนิพจน์ทั้งหมดแล้ว ผลลัพธ์สุดท้ายจะถูกเก็บไว้ในสแต็กด้านบนด้วย ดังนั้นหากนิพจน์คือ “53+62/*35*+” คำตอบจะเป็น 39

ให้เราดูขั้นตอน -

• สำหรับแต่ละอักขระ ch ในนิพจน์ postfix ให้ทำ
  • ถ้า ch เป็นโอเปอเรเตอร์ ☉ แล้ว
    • a :=ป๊อปองค์ประกอบแรกจากสแต็ก
    • b :=ป๊อปองค์ประกอบที่สองจากสแต็ก
    • res :=b ☉ a
    • ดัน res ลงใน stack
  • มิฉะนั้น ถ้า ch เป็นตัวถูกดำเนินการ แล้ว
    • เพิ่ม ch ลงในสแต็ก
• ส่งคืนองค์ประกอบของ stack top

ตัวอย่าง(C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อทำความเข้าใจ −

#include#include#include#includeusing namespace std;float scanNum(char ch){ ค่า int; ค่า =ch; return float(value-'0');//return float from character}int isOperator(char ch){ if(ch =='+'|| ch =='-'|| ch =='*'|| return float(value-'0'); //return float from character}int isOperator(char ch){ if(ch =='+'|| ch =='-'|| ch =='*'||| ch =='/' || ch =='^') return 1;//character is an operator return -1;//not an operator}int isOperand(char ch){ if(ch>='0' &&ch <='9') return 1;//character เป็นตัวถูกดำเนินการ return -1;//not an operand}float operation(int a, int b, char op){ //ดำเนินการ if(op =='+ ') คืนค่า b+a; อื่น if(op =='-') ส่งคืน b-a; อื่น if(op =='*') ส่งคืน b*a; อื่น if(op =='/') คืนค่า b/a; อื่น if(op =='^') return pow(b,a); // ค้นหา b^a อื่นส่งคืน INT_MIN; // คืนค่าอินฟินิตี้เชิงลบ}float postfixEval (สตริง postfix) { int a, b; กอง  stk; string::iterator มัน; for(it=postfix.begin(); it!=postfix.end(); it++){ //อ่านองค์ประกอบและดำเนินการประเมิน postfix if(isOperator(*it) !=-1){ a =stk.top(); stk.pop(); b =stk.top(); stk.pop(); stk.push(การดำเนินการ(a, b, *มัน)); } อื่น if(isOperand(*it)> 0){ stk.push(scanNum(*it)); } } return stk.top();}main(){ string post ="53+62/*35*+"; cout <<"ผลลัพธ์คือ:"< 
อินพุต
 
"53+62/*35*+"
 
ผลลัพธ์
 
ผลลัพธ์คือ:39