สแต็กเป็นรายการที่ จำกัด การแทรกและการลบที่จะดำเนินการในตำแหน่งเดียวเท่านั้น ตำแหน่งนี้เป็นจุดสิ้นสุดของรายการที่เรียกว่าด้านบนของสแต็ก สำหรับการดำเนินการขั้นพื้นฐานของสแต็คมีการผลักและป๊อป อดีตคือการแทรกและหลังถูกลบ
สแต็คยังเป็นตาราง FIFO
มีการใช้งานสองประเภทของสแต็กหนึ่งคือการใช้อาร์เรย์และอีกประเภทหนึ่งคือการใช้รายการที่เชื่อมโยง
คลาสสาธารณะ MyArrayStack <E> {Private ArrayList <E> list = new ArrayList <> (); โมฆะสาธารณะกด (e e) {list.add (e); } สาธารณะ e pop () {return list.remove (list.size () - 1); } สาธารณะ e peek () {return list.get (list.size () - 1); } บูลีนสาธารณะ isempty () {return list.size () == 0; }} คลาสสาธารณะ MyLinkStack <E> {LinkedList <E> list = new LinkedList <> (); โมฆะสาธารณะกด (e e) {list.addlast (e); } สาธารณะ e pop () {return list.removelast (); } public e peek () {return list.getLast (); } บูลีนสาธารณะ isempty () {return list.size () == 0; - แอปพลิเคชันสแต็ก
สัญลักษณ์สมดุล
จากสตริงของรหัสเราตรวจสอบว่าวงเล็บในรหัสนี้สอดคล้องกับไวยากรณ์หรือไม่
ตัวอย่างเช่น: [{()}] สิ่งนี้ถูกกฎหมาย แต่ [{]} () ผิดกฎหมาย
ต่อไปนี้เป็นรหัสทดสอบ:
Balancesymbol ระดับสาธารณะ {บูลีนสาธารณะ isbalance (สตริงสตริง) {MyArrayStack <caricy> stack = new MyArraystack <> (); char [] array = string.tochararray (); สำหรับ (char ch: array) {if ("{[(" .indexof (ch)> = 0) {stack.push (ch);} อื่นถ้า ("}])" indexof (ch)> = 0) {ถ้า (ismatching (stack.peek (), ch)) {stack.pop (); }}} return stack.isempty (); } บูลีนส่วนตัว isMatching (ถ่าน peek, ถ่าน ch) {ถ้า ((peek == '{' && ch == '}') || (peek == '[' && ch == ']') || (peek == '(' && ch == '))) } return false; } โมฆะคงที่สาธารณะหลัก (สตริง [] args) {สัญลักษณ์ Balancesymbol = ใหม่ balancesymbol (); สตริงสตริง = "โมฆะคงที่สาธารณะหลัก (สตริง [] args) {สัญลักษณ์ Balancesymbol = new Balancesymbol ();}"; String String2 = "โมฆะคงที่สาธารณะหลัก (สตริง [] args) {สัญลักษณ์ Balancesymbol = ใหม่ balancesymbol ([);}]"; System.out.println (Symbol.isbalance (String)); System.out.println (Symbol.isbalance (String2)); - การแสดงออกของคำต่อท้าย
ตัวอย่างเช่นอินพุตต่อไปนี้คำนวณผลลัพธ์ที่สอดคล้องกัน
3 + 2 + 3 * 2 =?
สิ่งนี้จะให้ผลลัพธ์ที่แตกต่างกันในลำดับการคำนวณที่แตกต่างกัน หากผลการคำนวณคือ 16 จากซ้ายไปขวาและหากผลการคำนวณเป็น 11 ตามลำดับความสำคัญทางคณิตศาสตร์
หากนิพจน์ Infix ข้างต้นถูกแปลงเป็นนิพจน์ต่อท้าย:
3 2 + 3 2 * +
มันจะง่ายมากในการคำนวณค่าของนิพจน์นี้โดยใช้นิพจน์ต่อท้ายเพียงแค่ใช้สแต็ก
เมื่อใดก็ตามที่พบตัวเลขให้ใส่หมายเลขบนสแต็ก
เมื่อใดก็ตามที่ผู้ประกอบการพบองค์ประกอบสององค์ประกอบจะปรากฏขึ้นเพื่อคำนวณตามตัวดำเนินการแล้ววางไว้บนสแต็ก
องค์ประกอบเดียวที่ปรากฏขึ้นสแต็กคือผลการคำนวณ
/*** เวอร์ชันที่เรียบง่ายแต่ละตัวถูกดำเนินการเป็นเพียงหนึ่งเดียวและสมมติว่าสตริงเป็นกฎหมาย*/คลาสสาธารณะ postfixExpression {public Static int คำนวณ (สตริงสตริง) {MyArrayStack <String> stack = new MyArraystack <> (); char [] arr = string.tochararray (); สำหรับ (char ch: arr) {ถ้า ("0123456789" .indexof (ch)> = 0) {stack.push (ch + ""); } อื่นถ้า ("+-*/". indexof (ch)> = 0) {int a = integer.parseint (stack.pop ()); int b = integer.parseint (stack.pop ()); if (ch == ' +') {stack.push ((a + b) + ""); } อื่นถ้า (ch == ' -') {stack.push ((a - b) + ""); } อื่นถ้า (ch == ' *') {stack.push ((a * b) + ""); } อื่นถ้า (ch == ' /') {stack.push ((a / b) + ""); }} return integer.parseint (stack.peek ()); } โมฆะคงที่สาธารณะหลัก (สตริง [] args) {system.out.println (คำนวณ ("32+32*+")); - แปลงนิพจน์ infix เป็นนิพจน์ต่อท้าย
สมมติว่ามีเพียงการแสดงออก +, -, *, /, () และการแสดงออกนั้นถูกกฎหมาย
a + b * c - (d * e + f) / g นิพจน์ต่อท้ายที่แปลงแล้วมีดังนี้:
abc * + de * f + g / -
ขั้นตอนในการใช้สแต็ก Infix เพื่อแปลงคำต่อท้ายมีดังนี้:
นำเข้า java.util.hashmap; นำเข้า java.util.map; Public Class Expressionswitch {แผนที่คงที่ส่วนตัว <ตัวละคร, จำนวนเต็ม> แผนที่ = ใหม่ hashmap <ตัวละคร, จำนวนเต็ม> (); คงที่ {map.put ('+', 0); map.put ('-', 1); map.put ('*', 2); map.put ('/', 3); map.put ('(', 4);} ตัวถ่านแบบคงที่ส่วนตัว [] [] ลำดับความสำคัญ = {// ตัวดำเนินการปัจจุบัน // + - */(/ * สแต็ก + */{'>', '>', '<', '<', '<'},/ * top- */{','> ' '>', '>', '<'},/ * make/ */{'>', '>', '>', '>', '<'},/ * อักขระ ( */{'<', '<', '<', '<', '<'},}; String.toChararray (); stack.push (ch); stack.push (ch); } return builder.toString (); } บูลีนคงที่ส่วนตัว ispriorityHigh (ถ่าน tmp, char ch) {ลำดับความสำคัญกลับ [map.get (tmp)] [map.get (ch)] == '>'; } โมฆะคงที่สาธารณะหลัก (สตริง [] args) {system.out.println (switch1 ("a+b*c- (d*e+f)/g")); -ผ่านบทความนี้ฉันหวังว่าทุกคนจะเชี่ยวชาญความรู้เกี่ยวกับ Java Stack ขอบคุณสำหรับการสนับสนุนเว็บไซต์นี้!