โปรแกรม C++ ประเมินนิพจน์ด้วย Stack

เพื่อแก้สมการทางคณิตศาสตร์ เราต้องการรูปแบบ prefix หรือ postfix หลังจากแปลง infix เป็น postfix แล้ว เราต้องใช้อัลกอริทึมประเมิน postfix เพื่อหาคำตอบที่ถูกต้อง ที่นี่เราก็ต้องใช้โครงสร้างข้อมูล stack เพื่อแก้สมการ postfix

จากนิพจน์ postfix เมื่อพบตัวถูกดำเนินการ (operand) ให้ push เข้า stack เมื่อพบตัวดำเนินการ (operator) ให้ pop สองรายการจาก stack แล้วดำเนินการในลำดับที่ถูกต้อง หลังจากนั้นผลลัพธ์ก็จะถูก push เข้า stack อีกครั้งเพื่อใช้ในอนาคต หลังจากประมวลผลนิพจน์ทั้งหมด ผลลัพธ์สุดท้ายก็จะอยู่ที่จุดบนสุดของ stack

Input: Postfix expression: 53+62/*35*+
Output: ผลลัพธ์คือ: 39

อัลกอริทึม

postfixEvaluation(postfix)

Input: นิพจน์ postfix ที่ต้องการประเมิน

Output: คำตอบหลังจากประเมินรูปแบบ postfix

Begin
    สำหรับแต่ละตัวอักษร ch ในนิพจน์ postfix ทำ
        ถ้า ch เป็น operator แล้ว
            a := pop องค์ประกอบแรกจาก stack
            b := pop องค์ประกอบที่สองจาก stack
            res := b operator a
            push res เข้า stack
        ไม่เช่นนั้น ถ้า ch เป็น operand แล้ว
            เพิ่ม ch เข้า stack
    จบ for
    return องค์ประกอบที่จุดบนสุดของ stack
End

ตัวอย่างโค้ด

#include <iostream>
#include <cmath>
#include <stack>
using namespace std;

float scanNum(char ch) {
    int value;
    value = ch;
    return float(value-'0'); // คืนค่า float จากตัวอักษร
}

int isOperator(char ch) {
    if(ch == '+'|| ch == '-'|| ch == '*'|| ch == '/' || ch == '^')
        return 1; // ตัวอักษรเป็น operator
    return -1; // ไม่ใช่ operator
}

int isOperand(char ch) {
    if(ch >= '0' && ch <= '9')
        return 1; // ตัวอักษรเป็น operand
    return -1; // ไม่ใช่ operand
}

float operation(int a, int b, char op) {
    // ดำเนินการคำนวณ
    if(op == '+')
        return b+a;
    else if(op == '-')
        return b-a;
    else if(op == '*')
        return b*a;
    else if(op == '/')
        return b/a;
    else if(op == '^')
        return pow(b,a); // หา b^a
    else
        return INT_MIN; // คืนค่าลบอนันต์
}

float postfixEval(string postfix) {
    int a, b;
    stack<float> stk;
    string::iterator it;
    
    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(operation(a, b, *it));
        }else if(isOperand(*it) > 0) {
            stk.push(scanNum(*it));
        }
    }
    return stk.top();
}

main() {
    string post = "53+62/*35*+";
    cout << "The result is: "<<postfixEval(post);
}

ผลลัพธ์

The result is: 39