นิพจน์ Infix สามารถอ่านและแก้ไขได้โดยมนุษย์ เราสามารถแยกแยะลำดับของตัวดำเนินการได้อย่างง่ายดาย และยังสามารถใช้วงเล็บเพื่อแก้ส่วนนั้นก่อนในระหว่างการแก้นิพจน์ทางคณิตศาสตร์ คอมพิวเตอร์ไม่สามารถแยกความแตกต่างระหว่างโอเปอเรเตอร์และวงเล็บได้ง่ายๆ ดังนั้นจึงจำเป็นต้องมีการแปลงหลังการแก้ไข
ในการแปลงนิพจน์ infix เป็นนิพจน์ postfix เราจะใช้โครงสร้างข้อมูลสแต็ก โดยการสแกนนิพจน์ infix จากซ้ายไปขวา เมื่อเราได้ตัวถูกดำเนินการใดๆ เพียงแค่เพิ่มลงในแบบฟอร์ม postfix และสำหรับโอเปอเรเตอร์และวงเล็บ ให้เพิ่มลงในสแต็กโดยคงลำดับความสำคัญไว้
หมายเหตุ: เราจะพิจารณาเฉพาะตัวดำเนินการ {+, −,∗,/, ^} เท่านั้น ส่วนตัวดำเนินการอื่นๆ จะถูกละเลย
อินพุตและเอาต์พุต
Input: The infix expression. x^y/(5*z)+2 Output: Postfix Form Is: xy^5z*/2+
อัลกอริทึม
infixToPostfix(infix)
ป้อนข้อมูล - นิพจน์ Infix
ผลลัพธ์ − แปลงนิพจน์ infix เป็นรูปแบบ postfix
Begin initially push some special character say # into the stack for each character ch from infix expression, do if ch is alphanumeric character, then add ch to postfix expression else if ch = opening parenthesis (, then push ( into stack else if ch = ^, then //exponential operator of higher precedence push ^ into the stack else if ch = closing parenthesis ), then while stack is not empty and stack top ≠ (, do pop and add item from stack to postfix expression done pop ( also from the stack else while stack is not empty AND precedence of ch <= precedence of stack top element, do pop and add into postfix expression done push the newly coming character. done while the stack contains some remaining characters, do pop and add to the postfix expression done return postfix End
ตัวอย่าง
#include<iostream> #include<stack> #include<locale> //for function isalnum() using namespace std; int preced(char ch) { if(ch == '+' || ch == '-') { return 1; //Precedence of + or - is 1 }else if(ch == '*' || ch == '/') { return 2; //Precedence of * or / is 2 }else if(ch == '^') { return 3; //Precedence of ^ is 3 }else { return 0; } } string inToPost(string infix ) { stack<char> stk; stk.push('#'); //add some extra character to avoid underflow string postfix = ""; //initially the postfix string is empty string::iterator it; for(it = infix.begin(); it!=infix.end(); it++) { if(isalnum(char(*it))) postfix += *it; //add to postfix when character is letter or number else if(*it == '(') stk.push('('); else if(*it == '^') stk.push('^'); else if(*it == ')') { while(stk.top() != '#' && stk.top() != '(') { postfix += stk.top(); //store and pop until ( has found stk.pop(); } stk.pop(); //remove the '(' from stack }else { if(preced(*it) > preced(stk.top())) stk.push(*it); //push if precedence is high else { while(stk.top() != '#' && preced(*it) <= preced(stk.top())) { postfix += stk.top(); //store and pop until higher precedence is found stk.pop(); } stk.push(*it); } } } while(stk.top() != '#') { postfix += stk.top(); //store and pop until stack is not empty. stk.pop(); } return postfix; } int main() { string infix = "x^y/(5*z)+2"; cout << "Postfix Form Is: " << inToPost(infix) << endl; }
ผลลัพธ์
Postfix Form Is: xy^5z*/2+