Infix в Postfix с использованием разных значений приоритета для In-Stack и Out-Stack

Опубликовано: 5 Января, 2022

Преобразование инфикса в постфиксное выражение может быть выполнено элегантно, используя две функции приоритета. Каждому оператору присваивается значение (большее значение означает более высокий приоритет), которое зависит от того, находится ли оператор внутри стека или вне его. Также правую и левую ассоциативность для разных операторов можно обрабатывать, изменяя ее значения в двух функциях приоритета.
Пример инфиксного выражения: a + b * c
Соответствующее ему постфиксное выражение : abc * +
Чтобы узнать больше об инфиксных и постфиксных выражениях, посетите ссылки.

Примечание: в этой статье мы предполагаем, что все операторы ассоциативны слева направо.
Примеры:

Input: str = “a+b*c-(d/e+f*g*h)”
Output: abc*+de/fg*h*+-
Input: a+b*c
Output: abc*+

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход:

Если вводимый символ является операндом, распечатайте его.
Если вводимый символ является оператором -
- Если стек пуст, поместите его в стек.
- Если его значение приоритета больше, чем значение приоритета верхнего символа, нажмите.
- Если его значение приоритета меньше или равно, тогда извлекать из стека и печатать, в то время как приоритет верхнего символа больше, чем значение приоритета входного символа.
Если вводимый символ - ')', то выталкивайте и печатайте до тех пор, пока верхний не станет '('. (Pop '(', но не печатайте его.)
Если стек становится пустым до появления символа '(', то это недопустимое выражение.
Повторяйте шаги 1–4, пока входное выражение не будет полностью прочитано.
Вытащите оставшиеся элементы из стопки и распечатайте их.

Вышеупомянутый метод обрабатывает правую ассоциативность оператора возведения в степень (здесь ^), присваивая ему более высокое значение приоритета вне стека и более низкое значение приоритета внутри стека, тогда как это противоположно для левоассоциативных операторов.

Ниже представлена реализация описанного выше подхода:

C ++

 // C++ program to convert an infix expression to a
 // postfix expression using two precedence function
 #include <bits/stdc++.h>
 using namespace std;
 
// to check if the input character
 // is an operator or a '('
 int isOperator( input) char
 {
    switch (input) {
    case '+' :
        return 1;
    case '-' :
        return 1;
    case '*' :
        return 1;
    case '%' :
        return 1;
    case '/' :
        return 1;
    case '(' :
        return 1;
    }
    return 0;
 }
 
// to check if the input character is an operand
 int isOperand( input) char
 {
    if (input >= 65 && input <= 90
        || input >= 97 && input <= 122)
        return 1;
    return 0;
 }
 
// function to return precedence value
 // if operator is present in stack
 int inPrec( input) char
 {
    switch (input) {
    case '+' :
    case '-' :
        return 2;
    case '*' :
    case '%' :
    case '/' :
        return 4;
    case '(' :
        return 0;
    }
 }
 
// function to return precedence value
 // if operator is present outside stack.
 int outPrec( input) char
 {
    switch (input) {
    case '+' :
    case '-' :
        return 1;
    case '*' :
    case '%' :
    case '/' :
        return 3;
    case '(' :
        return 100;
    }
 }
 
// function to convert infix to postfix
 void inToPost( char * input)
 {
    stack< char > s;
 
    // while input is not NULL iterate
    int i = 0;
    while (input[i] != '' ) {
 
        // if character an operand
        if (isOperand(input[i])) {
            printf ( "%c" , input[i]);
        }
 
        // if input is an operator, push
        else if (isOperator(input[i])) {
            if (s.empty()
                || outPrec(input[i]) > inPrec(s.top()))
                s.push(input[i]);
            else {
                while (!s.empty()
                    && outPrec(input[i]) < inPrec(s.top())) {
                    printf ( "%c" , s.top());
                    s.pop();
                }
                s.push(input[i]);
            }
        }
 
        // condition for opening bracket
        else if (input[i] == ')' ) {
            while (s.top() != '(' ) {
                printf ( "%c" , s.top());
                s.pop();
 
                // if opening bracket not present
                if (s.empty()) {
                    printf ( "Wrong input
" );
                    exit (1);
                }
            }
 
            // pop the opening bracket.
            s.pop();
        }
        i++;
    }
 
    // pop the remaining operators
    while (!s.empty()) {
        if (s.top() == '(' ) {
            printf ( "
 Wrong input
" );
            exit (1);
        }
        printf ( "%c" , s.top());
        s.pop();
    }
 }
 
// Driver code
 int main()
 {
    char input[] = "a+b*c-(d/e+f*g*h)" ;
    inToPost(input);
    return 0;
 }

Джава

 import static java.lang.System.exit;
 import java.util.Stack;
 
// Java program to convert an infix expression to a
 // postfix expression using two precedence function
 class GFG {
 
    // to check if the input character
    // is an operator or a '('
    static int isOperator( input) char
    {
        switch (input) {
        case '+' :
            return 1 ;
        case '-' :
            return 1 ;
        case '*' :
            return 1 ;
        case '%' :
            return 1 ;
        case '/' :
            return 1 ;
        case '(' :
            return 1 ;
        }
        return 0 ;
    }
 
    // to check if the input character is an operand
    static int isOperand( input) char
    {
        if (input >= 65 && input <= 90
            || input >= 97 && input <= 122 ) {
            return 1 ;
        }
        return 0 ;
    }
 
    // function to return precedence value
    // if operator is present in stack
    static int inPrec( input) char
    {
        switch (input) {
        case '+' :
        case '-' :
            return 2 ;
        case '*' :
        case '%' :
        case '/' :
            return 4 ;
        case '(' :
            return 0 ;
        }
        return 0 ;
    }
 
    // function to return precedence value
    // if operator is present outside stack.
    static int outPrec( input) char
    {
        switch (input) {
        case '+' :
        case '-' :
            return 1 ;
        case '*' :
        case '%' :
        case '/' :
            return 3 ;
        case '(' :
            return 100 ;
        }
        return 0 ;
    }
 
    // function to convert infix to postfix
    static void inToPost( char [] input)
    {
        Stack<Character> s = new Stack<Character>();
 
        // while input is not NULL iterate
        int i = 0 ;
        while (input.length != i) {
 
            // if character an operand
            if (isOperand(input[i]) == 1 ) {
                System.out.printf( "%c" , input[i]);
            } // if input is an operator, push
            else if (isOperator(input[i]) == 1 ) {
                if (s.empty()
                    || outPrec(input[i]) > inPrec(s.peek())) {
                    s.push(input[i]);
                }
                else {
                    while (!s.empty()
                           && outPrec(input[i]) < inPrec(s.peek())) {
                        System.out.printf( "%c" , s.peek());
                        s.pop();
                    }
                    s.push(input[i]);
                }
            } // condition for opening bracket
            else if (input[i] == ')' ) {
                while (s.peek() != '(' ) {
                    System.out.printf( "%c" , s.peek());
                    s.pop();
 
                    // if opening bracket not present
                    if (s.empty()) {
                        System.out.printf( "Wrong input
" );
                        exit( 1 );
                    }
                }
 
                // pop the opening bracket.
                s.pop();
            }
            i++;
        }
 
        // pop the remaining operators
        while (!s.empty()) {
            if (s.peek() == '(' ) {
                System.out.printf( "
 Wrong input
" );
                exit( 1 );
            }
            System.out.printf( "%c" , s.peek());
            s.pop();
        }
    }
 
    // Driver code
    static public void main(String[] args)
    {
        char input[] = "a+b*c-(d/e+f*g*h)" .toCharArray();
        inToPost(input);
    }
 }
 
// This code is contributed by Rajput-Ji

Python3

 # Python3 program to convert an infix
 # expression to a postfix expression
 # using two precedence function
 
# To check if the input character
 # is an operator or a '('
 def isOperator( input ):
     
    switch = {
        '+' : 1 ,
        '-' : 1 ,
        '*' : 1 ,
        '/' : 1 ,
        '%' : 1 ,
        '(' : 1 ,
    }
     
    return switch.get( input , False )
 
# To check if the input character is an operand
 def isOperand( input ):
     
    if (( ord ( input ) > = 65 and ord ( input ) < = 90 ) or
        ( ord ( input ) > = 97 and ord ( input ) < = 122 )):
        return 1
         
    return 0
 
# Function to return precedence value
 # if operator is present in stack
 def inPrec( input ):
     
    switch = {
        '+' : 2 ,
        '-' : 2 ,
        '*' : 4 ,
        '/' : 4 ,
        '%' : 4 ,
        '(' : 0 ,
    }
     
    return switch.get( input , 0 )
 
# Function to return precedence value
 # if operator is present outside stack.
 def outPrec( input ):
     
    switch = {
        '+' : 1 ,
        '-' : 1 ,
        '*' : 3 ,
        '/' : 3 ,
        '%' : 3 ,
        '(' : 100 ,
    }
     
    return switch.get( input , 0 )
 
# Function to convert infix to postfix
 def inToPost( input ):
     
    i = 0
    s = []
 
    # While input is not NULL iterate
    while ( len ( input ) ! = i):
 
        # If character an operand
        if (isOperand( input [i]) = = 1 ):
            print ( input [i], end = "")
 
        # If input is an operator, push
        elif (isOperator( input [i]) = = 1 ):
            if ( len (s) = = 0 or
                outPrec( input [i]) >
                 inPrec(s[ - 1 ])):
                s.append( input [i])
             
            else :
                while ( len (s) > 0 and
                      outPrec( input [i]) <
                      inPrec(s[ - 1 ])):
                    print (s[ - 1 ], end = "")
                    s.pop()
                     
                s.append( input [i])
 
        # Condition for opening bracket
        elif ( input [i] = = ')' ):
            while (s[ - 1 ] ! = '(' ):
                print (s[ - 1 ], end = "")
                s.pop()
 
                # If opening bracket not present
                if ( len (s) = = 0 ):
                    print ( 'Wrong input' )
                    exit( 1 )
 
            # pop the opening bracket.
            s.pop()
             
        i+=1
                    
                                            Technical Scripter
                                    
РЕКОМЕНДУЕМЫЕ СТАТЬИКоличество чисел между L и R, взаимно простых с P
27 Февраля, 2023
Постройте матрицу, каждая строка и столбец которой содержат N и M единиц соответственно.
27 Февраля, 2023
Максимизируйте сумму трех чисел, выполнив побитовое XOR
27 Февраля, 2023
Проверьте, совпадает ли набор первых элементов X одного массива с набором первых элементов Y другого
27 Февраля, 2023
Подсчитать подстроки нечетной длины с медианой, такой же, как K-й символ строки
27 Февраля, 2023
Найти лексикографически первый идентификатор каждого домена из заданного массива идентификаторов электронной почты
27 Февраля, 2023
Найдите общее количество фигур 'X'
26 Февраля, 2023
Максимальное значение узла, которое может быть достигнуто с использованием данных соединений
26 Февраля, 2023

                    < PROGLER >

                

                    Общее
Контакты
Политика конфиденциальности

                    Обучение
Блог

                

                © progler.ru 2024. Все права защищены.
            