เมื่อเขียนโค้ดบางครั้งเราพบสถานการณ์ที่เราต้องแยกวิเคราะห์การแสดงออกทางคณิตศาสตร์ทั้งสี่ด้วยตัวเอง บทความนี้แนะนำการใช้ JavaScript สั้น ๆ เพื่อใช้การแยกวิเคราะห์การแสดงออกทางคณิตศาสตร์สี่แบบง่าย ๆ
1. คุ้นเคยกับแนวคิด
สัญกรณ์ Infix (หรือสัญกรณ์ Infix) เป็นวิธีการแสดงสูตรทางคณิตศาสตร์ทั่วไปหรือแบบตรรกะ ผู้ประกอบการอยู่ตรงกลางของตัวถูกดำเนินการในรูปแบบของ infix (ตัวอย่าง: 3 + 4) นั่นคือเราใช้การแสดงออกทางคณิตศาสตร์ที่ใช้กันมากที่สุด การแสดงออกของ Infix นั้นง่ายกว่าสำหรับมนุษย์ที่จะเข้าใจ แต่ไม่ใช่เรื่องง่ายสำหรับการวิเคราะห์คอมพิวเตอร์
Reverse Polish Notation (RPN หรือ Inverse Polish Notation) เป็นวิธีการแสดงออกทางคณิตศาสตร์ที่แนะนำโดย Jan Vukasevich นักคณิตศาสตร์ชาวโปแลนด์ในปี 1920 ในสัญกรณ์ชาวโปแลนด์ผกผัน สัญกรณ์ผกผันโปแลนด์ไม่จำเป็นต้องใช้วงเล็บเพื่อระบุลำดับความสำคัญของผู้ปฏิบัติงาน สัญกรณ์ผกผันโปแลนด์เป็นเรื่องง่ายที่จะใช้โครงสร้างสแต็กเพื่อแยกวิเคราะห์และคำนวณการแสดงออกดังนั้นที่นี่เราแยกวิเคราะห์การแสดงออกขององค์ประกอบทั้งสี่ซึ่งแปลงจากนิพจน์ Infix เป็นนิพจน์ของโปแลนด์ผกผัน จากนั้นคำนวณค่า
2. กระบวนการแปลง
แปลงนิพจน์ Infix เป็นนิพจน์ต่อท้าย (อัลกอริทึมฟิลด์กำหนดเวลา)
1. ป้อนคิวและปรากฏเครื่องหมาย
2. หากเครื่องหมายเป็นตัวเลขให้เพิ่มลงในคิวเอาต์พุต
3. ถ้าเป็นตัวดำเนินการ (+-*/) ให้เปรียบเทียบกับตัวดำเนินการที่ด้านบนของสแต็กในสแต็กเอาต์พุต หากลำดับความสำคัญน้อยกว่าหรือเท่ากับตัวดำเนินการที่ด้านบนของสแต็กให้ปรากฏตัวขึ้นผู้ประกอบการที่ด้านบนของสแต็กและเพิ่มลงในคิวเอาต์พุต (วนรอบจนกว่าเงื่อนไขข้างต้นจะไม่เป็นไปตาม)
4. ถ้าเป็นตัวยึดซ้ายให้ดันเข้าไปในสแต็ก
5. ถ้าเป็นตัวยึดอย่างใกล้ชิดผู้ประกอบการจะถูกผุดออกมาอย่างต่อเนื่องจากสแต็กและเพิ่มลงในคิวเอาท์พุทและรู้ว่าองค์ประกอบที่ด้านบนของสแต็กคือวงเล็บซ้าย ตัวยึดซ้ายปรากฏขึ้นและไม่เพิ่มคิวเอาต์พุต หากไม่พบวงเล็บซ้ายหมายความว่าวงเล็บในนิพจน์ดั้งเดิมนั้นไม่สมมาตรและมีข้อผิดพลาด
6. หากคิวอินพุตว่างเปล่าและยังมีตัวดำเนินการในสแต็กหากผู้ปฏิบัติงานที่ด้านบนของสแต็กนั้นถูกยึดไว้ก็หมายความว่านิพจน์ดั้งเดิมนั้นมีวงเล็บที่ไม่ตรงกัน เปิดตัวดำเนินการในสแต็คทีละตัวแล้วเพิ่มลงในคิวเอาท์พุท
7. เสร็จสิ้น
3. แปลงการใช้งานรหัส
ฟังก์ชั่น isoperator (ค่า) {var operatorsTring = "+-*/()"; return operatorsTring.indexof (value)> -1} ฟังก์ชั่น getPrioraty (ค่า) {สวิตช์ (ค่า) {case '+': case '-': return 1; case '*' getPrioraty (O2);} ฟังก์ชั่น dal2rpn (exp) {var inputstack = []; var outputstack = []; var outputqueue = []; สำหรับ (var i = 0, len = exp.length; i <len; i ++) {var cur = exp [i] หนึ่ง'); ในขณะที่ (inputstack.length> 0) {var cur = inputstack.shift (); ถ้า (isoperator (cur)) {ถ้า (cur == '(') {outputstack.push (cur);} อื่นถ้า (cur == ')') {var po = outputStack.pop (); ในขณะที่ (po! = '(' && outputstack.length> 0) {outputqueue.push (po); po = outputstack.pop ();} ถ้า (po! = '(') {โยน "ข้อผิดพลาด: unmatched ()";}}} 0) {outputqueue.push (outputstack.pop ());} outputstack.push (cur);}} else {outputqueue.push (หมายเลขใหม่ (cur));}} console.log ('ขั้นตอนที่สอง') OutputStack [OutputStack.length - 1] == '(') {โยน "ข้อผิดพลาด: unmatched ()";} ในขณะที่ (outputstack.length> 0) {outputqueue.push (outputstack.pop ());}} console.log ('สาม') 2 ')); console.log (dal2rpn (' 1 + 2 + 3 ')); console.log (dal2rpn (' 1 + 2 * 3 ')); console.log (dal2rpn (' 1 + 2 * 3 - 4 /5 ')); console.log 2) * (3 - 4) / 5 ')); console.log (dal2rpn (' (1 + 2) * ((3 - 4) / 5) '));4. การประเมินการแสดงออกแบบผกผันโปแลนด์
1. ป๊อปอัพเครื่องหมายจากคิวอินพุต
2. ถ้าเป็นตัวถูกดำเนินการให้เพิ่มลงในสแต็กเอาต์พุต
3. หากเป็นตัวดำเนินการให้เปิดสองตัวถูกดำเนินการจากสแต็กเอาท์พุทและคำนวณและผลักดันค่าที่คำนวณไว้ในสแต็กเอาต์พุต
4. การดำเนินการวนรอบ หากคิวอินพุตว่างเปล่าและมีเพียงหมายเลขเดียวในสแต็กเอาต์พุตตัวเลขนี้เป็นผลลัพธ์ไม่เช่นนั้นจะมีตัวถูกดำเนินการที่ไม่จำเป็น
5. คำนวณรหัส
ฟังก์ชั่น evalrpn (rpnqueue) {var outputstack = []; ในขณะที่ (rpnqueue.length> 0) {var cur = rpnqueue.shift (); ถ้า (! isoperator (cur)) {outputstack.push (cur); outputstack.pop (); var fir = outputstack.pop (); outputstack.push (getResult (fir, sec, cur));}} ถ้า (outputstack.length! = 1) {โยน "unvalid expression";6. บทสรุป
การเป็นตัวแทนของการขัดแบบผกผันไม่ได้ใช้เมื่อคุณติดต่อกับมันเป็นครั้งแรก แต่หลังจากทำความคุ้นเคยกับมันคุณจะพบว่าความคิดนั้นง่ายมากซึ่งแตกต่างจากการเป็นตัวแทน Infix ซึ่งมีลำดับความสำคัญที่หลากหลายและมีวงเล็บซึ่งเป็นตรรกะที่ลำบากโดยเฉพาะ การเป็นตัวแทนของการขัดแบบผกผันนั้นค่อนข้างรัดกุมและไม่จำเป็นต้องพิจารณาลำดับความสำคัญเลยและไม่จำเป็นต้องใช้วงเล็บและวงเล็บและวงเล็บปีกกาเพื่อขัดขวางสถานการณ์