Java Technologies Stack এর ব্যবহার (Balanced Parentheses, Infix to Postfix) গাইড ও নোট

Stack হল একটি লিনিয়ার ডাটা স্ট্রাকচার যা LIFO (Last In First Out) ভিত্তিতে কাজ করে। অর্থাৎ, একটি উপাদান স্ট্যাকের শীর্ষে (top) যুক্ত হলে, প্রথমে সেই উপাদানটি বের করা হয়। স্ট্যাকের প্রধান অপারেশনগুলির মধ্যে রয়েছে push(), pop(), peek() এবং isEmpty()। স্ট্যাক অনেক ধরনের সমস্যার সমাধানে ব্যবহার করা হয়, যেমন Balanced Parentheses Checking এবং Infix to Postfix Conversion।

এই টিউটোরিয়ালে, আমরা দুটি জনপ্রিয় স্ট্যাক সমস্যার সমাধান দেখব:

1. Balanced Parentheses Checking
2. Infix to Postfix Conversion

1. Balanced Parentheses Checking

Balanced Parentheses Checking সমস্যা হল, একটি স্ট্রিংয়ের মধ্যে সমস্ত বন্ধনী সঠিকভাবে বন্ধ হয়েছে কিনা তা পরীক্ষা করা। উদাহরণস্বরূপ, "()", "(())", এবং "({[]})" এগুলি সঠিকভাবে বন্ধনীবদ্ধ স্ট্রিং, তবে "(()" এবং ")(" এর মধ্যে সঠিকভাবে বন্ধনী নেই।

উদাহরণ: Balanced Parentheses Checking

import java.util.Stack;

public class BalancedParentheses {
    public static void main(String[] args) {
        String expression = "{[()]}";
        if (isBalanced(expression)) {
            System.out.println("The parentheses are balanced.");
        } else {
            System.out.println("The parentheses are not balanced.");
        }
    }

    // Function to check if parentheses are balanced
    public static boolean isBalanced(String expression) {
        Stack<Character> stack = new Stack<>();

        // Iterate through the expression
        for (char ch : expression.toCharArray()) {
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);  // Push opening brackets onto the stack
            } else if (ch == ')' || ch == '}' || ch == ']') {
                // Check if stack is empty or if the top doesn't match
                if (stack.isEmpty()) {
                    return false;  // Closing bracket without matching opening bracket
                }
                char top = stack.pop();
                if (!isMatchingPair(top, ch)) {
                    return false;  // Mismatched parentheses
                }
            }
        }
        return stack.isEmpty();  // If stack is empty, parentheses are balanced
    }

    // Helper function to check if the pair of parentheses is valid
    public static boolean isMatchingPair(char opening, char closing) {
        return (opening == '(' && closing == ')') || 
               (opening == '{' && closing == '}') || 
               (opening == '[' && closing == ']');
    }
}

ব্যাখ্যা:

1. Stack ব্যবহার করে প্রতিটি ওপেনিং প্যারেন্টেসিস যেমন (, {, [ স্ট্যাকে পুশ করা হয়।
2. প্রতিটি ক্লোজিং প্যারেন্টেসিস যেমন ), }, ] পাওয়া গেলে, স্ট্যাক থেকে একটি এলিমেন্ট পপ করা হয় এবং এটি চেক করা হয় যে এটি সঠিক ওপেনিং প্যারেন্টেসিসের সাথে মেলে কি না।
3. শেষে, স্ট্যাক যদি খালি থাকে, তবে স্ট্রিংটি balanced এবং যদি না থাকে, তবে এটি unbalanced।

আউটপুট:

The parentheses are balanced.

2. Infix to Postfix Conversion

Infix to Postfix Conversion হল একটি সমস্যা যেখানে ইনফিক্স (প্রথাগত) এক্সপ্রেশনকে পোস্টফিক্স (Reverse Polish Notation) এক্সপ্রেশনে রূপান্তর করা হয়। ইনফিক্স এক্সপ্রেশনে অপারেটর অপার্যান্ডের মধ্যে থাকে, যেমন A + B। পোস্টফিক্সে, অপারেটরগুলো অপার্যান্ডের পরে আসে, যেমন A B +।

উদাহরণ: Infix to Postfix Conversion

import java.util.Stack;

public class InfixToPostfix {
    public static void main(String[] args) {
        String infixExpression = "A+B*(C^D-E)^(F+G*H)-I";
        System.out.println("Infix Expression: " + infixExpression);
        String postfixExpression = infixToPostfix(infixExpression);
        System.out.println("Postfix Expression: " + postfixExpression);
    }

    // Function to convert infix expression to postfix expression
    public static String infixToPostfix(String expression) {
        StringBuilder result = new StringBuilder();
        Stack<Character> stack = new Stack<>();

        // Iterate through the expression
        for (char ch : expression.toCharArray()) {
            // If the character is an operand, add it to the result
            if (Character.isLetterOrDigit(ch)) {
                result.append(ch);
            }
            // If the character is '(', push it to stack
            else if (ch == '(') {
                stack.push(ch);
            }
            // If the character is ')', pop and append until '(' is encountered
            else if (ch == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    result.append(stack.pop());
                }
                stack.pop();  // Remove '(' from stack
            }
            // If the character is an operator, pop operators with higher or equal precedence
            else {
                while (!stack.isEmpty() && precedence(ch) <= precedence(stack.peek())) {
                    result.append(stack.pop());
                }
                stack.push(ch);  // Push the current operator to stack
            }
        }

        // Pop all remaining operators from the stack
        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }

        return result.toString();
    }

    // Function to return precedence of operators
    public static int precedence(char operator) {
        switch (operator) {
            case '^': return 3;
            case '*':
            case '/': return 2;
            case '+':
            case '-': return 1;
            default: return -1;
        }
    }
}

ব্যাখ্যা:

1. Stack ব্যবহার করে ইনফিক্স এক্সপ্রেশনকে পোস্টফিক্স এক্সপ্রেশনে রূপান্তর করা হয়।
2. যদি একটি অপ্রচলিত অপার্যান্ড (অর্থাৎ, অক্ষর বা সংখ্যা) পাওয়া যায়, তা সরাসরি আউটপুটে যুক্ত করা হয়।
3. যদি একটি অপারেটর পাওয়া যায়, তবে সেগুলোকে স্ট্যাকে রাখা হয় এবং যতক্ষণ না স্ট্যাকের শীর্ষে একটি কম প্রাধান্যসম্পন্ন অপারেটর পাওয়া যায়, ততক্ষণ সেগুলো পপ করা হয়।
4. প্রাধান্য অনুযায়ী অপারেটরের গুরুত্ব নির্ধারণ করতে precedence() ফাংশন ব্যবহার করা হয়।

আউটপুট:

Infix Expression: A+B*(C^D-E)^(F+G*H)-I
Postfix Expression: ABCD^E-FGH*+^*+I-

সারাংশ

Stack ডাটা স্ট্রাকচারটি Balanced Parentheses Checking এবং Infix to Postfix Conversion এর মতো সমস্যা সমাধানের জন্য অত্যন্ত উপযোগী। Java তে স্ট্যাক ব্যবহার করে এই সমস্যাগুলো খুব সহজে এবং কার্যকরভাবে সমাধান করা যায়।

1. Balanced Parentheses Checking এর মাধ্যমে স্ট্যাকের সাহায্যে প্যারেন্টেসিসের সঠিকতা যাচাই করা যায়।
2. Infix to Postfix Conversion সমস্যা স্ট্যাক ব্যবহার করে ইনফিক্স এক্সপ্রেশনকে পোস্টফিক্স এক্সপ্রেশনে রূপান্তর করা হয়, যা পরবর্তীতে অ্যালগরিদমিক অপারেশনগুলো সহজতর করে।

Java তে স্ট্যাক ব্যবহার করে এই ধরনের সমস্যাগুলোর সমাধান করা সহজ এবং প্রোডাকটিভ হতে পারে।