Рубрики

Стек | Набор 4 (оценка выражения Postfix)

Стек

Запись Postfix используется для представления алгебраических выражений. Выражения, написанные в постфиксной форме, оцениваются быстрее по сравнению с Инфиксная запись в виде круглых скобок в постфиксе не требуется. Мы обсудили конверсию инфикса в постфикс . В этом посте обсуждается оценка выражений postfix.

Ниже приведен алгоритм оценки выражений постфикса.
1) Создать стек для хранения операндов (или значений).
2) Отсканируйте данное выражение и выполните следующие действия для каждого отсканированного элемента.
… ..A) Если элемент является числом, поместите его в стек
… ..B) Если элемент является оператором, выведите операнды для оператора из стека. Оцените оператора и перенесите результат обратно в стек
3) Когда выражение заканчивается, число в стеке является окончательным ответом

Пример:
Пусть заданное выражение будет «2 3 1 * + 9 -». Мы сканируем все элементы по одному.
1) Отсканируйте «2», это число, поэтому поместите его в стек. Стек содержит «2»
2) Отсканируйте «3», снова число, поместите его в стек, стек теперь содержит «2 3» (снизу вверх)
3) Отсканируйте «1», снова число, поместите его в стек, стек теперь содержит «2 3 1»
4) Сканирование '*', это оператор, извлечение двух операндов из стека, применение оператора * к операндам, мы получаем 3 * 1, что приводит к 3. Мы помещаем результат '3' в стек. Стек теперь становится «2 3».
5) Сканирование «+», это оператор, извлечение двух операндов из стека, применение оператора + к операндам, мы получаем 3 + 2, что приводит к 5. Мы помещаем результат «5» в стек. Стек теперь становится «5».
6) Отсканируйте «9», это число, мы помещаем его в стек. Стек теперь становится «5 9».
7) Сканирование '-', это оператор, извлечение двух операндов из стека, применение оператора — к операндам, мы получаем 5 — 9, что приводит к -4. Мы помещаем результат '-4' в стек. Стек теперь становится «-4».
8) Больше нет элементов для сканирования, мы возвращаем верхний элемент из стека (который является единственным элементом, оставшимся в стеке).

Ниже приведена реализация вышеуказанного алгоритма.

C ++

// C ++ программа для оценки значения выражения postfix
#include <iostream> 
#include <string.h> 

  

using namespace std;

  
// Тип стека

struct Stack 

{ 

    int top; 

    unsigned capacity; 

    int* array; 

}; 

  
// Стековые операции

struct Stack* createStack( unsigned capacity ) 

{ 

    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack)); 

  

    if (!stack) return NULL; 

  

    stack->top = -1; 

    stack->capacity = capacity; 

    stack->array = (int*) malloc(stack->capacity * sizeof(int)); 

  

    if (!stack->array) return NULL; 

  

    return stack; 

} 

  

int isEmpty(struct Stack* stack) 

{ 

    return stack->top == -1 ; 

} 

  

char peek(struct Stack* stack) 

{ 

    return stack->array[stack->top]; 

} 

  

char pop(struct Stack* stack) 

{ 

    if (!isEmpty(stack)) 

        return stack->array[stack->top--] ; 

    return '$'; 

} 

  

void push(struct Stack* stack, char op) 

{ 

    stack->array[++stack->top] = op; 

} 

  

  
// Основная функция, которая возвращает значение данного постфиксного выражения

int evaluatePostfix(char* exp) 

{ 

    // Создание стека емкости, равной размеру выражения

    struct Stack* stack = createStack(strlen(exp)); 

    int i; 

  

    // Посмотрим, был ли стек успешно создан

    if (!stack) return -1; 

  

    // Сканируем все символы по одному

    for (i = 0; exp[i]; ++i) 

    { 

        // Если отсканированный символ является операндом (число здесь),

        // положить его в стек.

        if (isdigit(exp[i])) 

            push(stack, exp[i] - '0'); 

  

        // Если отсканированный символ является оператором, выведите два

        // элементы из стека применяют оператор

        else

        { 

            int val1 = pop(stack); 

            int val2 = pop(stack); 

            switch (exp[i]) 

            { 

            case '+': push(stack, val2 + val1); break; 

            case '-': push(stack, val2 - val1); break; 

            case '*': push(stack, val2 * val1); break; 

            case '/': push(stack, val2/val1); break; 

            } 

        } 

    } 

    return pop(stack); 

} 

  
// Программа драйвера для проверки вышеуказанных функций

int main() 

{ 

    char exp[] = "231*+9-"; 

    cout<<"postfix evaluation: "<< evaluatePostfix(exp); 

    return 0; 

} 

С

// C-программа для оценки значения выражения postfix
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

  
// Тип стека

struct Stack

{

    int top;

    unsigned capacity;

    int* array;

};

  
// Стековые операции

struct Stack* createStack( unsigned capacity )

{

    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));

  

    if (!stack) return NULL;

  

    stack->top = -1;

    stack->capacity = capacity;

    stack->array = (int*) malloc(stack->capacity * sizeof(int));

  

    if (!stack->array) return NULL;

  

    return stack;

}

  

int isEmpty(struct Stack* stack)

{

    return stack->top == -1 ;

}

  

char peek(struct Stack* stack)

{

    return stack->array[stack->top];

}

  

char pop(struct Stack* stack)

{

    if (!isEmpty(stack))

        return stack->array[stack->top--] ;

    return '$';

}

  

void push(struct Stack* stack, char op)

{

    stack->array[++stack->top] = op;

}

  

  
// Основная функция, которая возвращает значение данного постфиксного выражения

int evaluatePostfix(char* exp)

{

    // Создание стека емкости, равной размеру выражения

    struct Stack* stack = createStack(strlen(exp));

    int i;

  

    // Посмотрим, был ли стек успешно создан

    if (!stack) return -1;

  

    // Сканируем все символы по одному

    for (i = 0; exp[i]; ++i)

    {

        // Если отсканированный символ является операндом (число здесь),

        // положить его в стек.

        if (isdigit(exp[i]))

            push(stack, exp[i] - '0');

  

        // Если отсканированный символ является оператором, выведите два

        // элементы из стека применяют оператор

        else

        {

            int val1 = pop(stack);

            int val2 = pop(stack);

            switch (exp[i])

            {

            case '+': push(stack, val2 + val1); break;

            case '-': push(stack, val2 - val1); break;

            case '*': push(stack, val2 * val1); break;

            case '/': push(stack, val2/val1); break;

            }

        }

    }

    return pop(stack);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    char exp[] = "231*+9-";

    printf ("postfix evaluation: %d", evaluatePostfix(exp));

    return 0;

}

Джава

// Java Proram для оценки значения выражения postfix

  

import java.util.Stack;

  

public class Test 

{

    // Метод для оценки значения выражения postfix

    static int evaluatePostfix(String exp)

    {

        // создаем стек

        Stack<Integer> stack=new Stack<>();

          

        // Сканируем все символы по одному

        for(int i=0;i<exp.length();i++)

        {

            char c=exp.charAt(i);

              

            // Если отсканированный символ является операндом (число здесь),

            // положить его в стек.

            if(Character.isDigit(c))

            stack.push(c - '0');

              

            // Если отсканированный символ является оператором, выведите два

            // элементы из стека применяют оператор

            else

            {

                int val1 = stack.pop();

                int val2 = stack.pop();

                  

                switch(c)

                {

                    case '+':

                    stack.push(val2+val1);

                    break;

                      

                    case '-':

                    stack.push(val2- val1);

                    break;

                      

                    case '/':

                    stack.push(val2/val1);

                    break;

                      

                    case '*':

                    stack.push(val2*val1);

                    break;

              }

            }

        }

        return stack.pop();    

    }

      

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args) 

    {

        String exp="231*+9-";

        System.out.println("postfix evaluation: "+evaluatePostfix(exp));

    }

}
// Предоставлено Сумит Гош

питон

# Программа Python для оценки значения выражения postfix

  
# Класс для преобразования выражения

class Evaluate:

      

    # Конструктор для инициализации переменных класса

    def __init__(self, capacity):

        self.top = -1

        self.capacity = capacity

        # Этот массив используется стеком

        self.array = []

      

    # проверить, пуст ли стек

    def isEmpty(self):

        return True if self.top == -1 else False

      

    # Вернуть значение вершины стека

    def peek(self):

        return self.array[-1]

      

    # Вытолкнуть элемент из стека

    def pop(self):

        if not self.isEmpty():

            self.top -= 1

            return self.array.pop()

        else:

            return "$"

      

    # Вставить элемент в стек

    def push(self, op):

        self.top += 1

        self.array.append(op) 

  

  

    # Основная функция, которая преобразует данное выражение инфикса

    # постфиксное выражение

    def evaluatePostfix(self, exp):

          

        # Перебрать выражение для преобразования

        for i in exp:

              

            # Если отсканированный символ является операндом

            # (число здесь) поместите его в стек

            if i.isdigit():

                self.push(i)

  

            # Если отсканированный символ является оператором,

            # вытолкнуть два элемента из стека и применить его.

            else:

                val1 = self.pop()

                val2 = self.pop()

                self.push(str(eval(val2 + i + val1)))

  

        return int(self.pop())

                  

  

              
# Программа драйвера для проверки вышеуказанной функции

exp = "231*+9-"

obj = Evaluate(len(exp))

print "postfix evaluation: %d"%(obj.evaluatePostfix(exp))

# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// C # proram для оценки значения выражения postfix

using System;

using System.Collections;

  

namespace GFG

{

    class Geek

    {

        // метод Main ()

        static void Main()

        {

            Geek e = new Geek();

            e.v = ("231*+9-");

            e.expression();

            Console.WriteLine("postfix evaluation: " + e.answer);

            Console.Read();

        }

  

        public string v;

        // 'v' является переменной для хранения строкового значения

  

        public string answer;

        Stack i = new Stack();

        // 'Stack ()' - встроенная функция для пространства имен 'System.Collections'

  

        public void expression()

        // метод оценки

        {

            int a, b, ans;

            for (int j = 0; j < v.Length; j++)

            //'v.Length 'означает длину строки

            {

                String c = v.Substring(j, 1);

                if (c.Equals("*"))

                {

                    String sa = (String)i.Pop();

                    String sb = (String)i.Pop();

                    a = Convert.ToInt32(sb);

                    b = Convert.ToInt32(sa);

                    ans = a * b;

                    i.Push(ans.ToString());

  

                }

                else if (c.Equals("/"))

                {

                    String sa = (String)i.Pop();

                    String sb = (String)i.Pop();

                    a = Convert.ToInt32(sb);

                    b = Convert.ToInt32(sa);

                    ans = a / b;

                    i.Push(ans.ToString());

                }

                else if (c.Equals("+"))

                {

                    String sa = (String)i.Pop();

                    String sb = (String)i.Pop();

                    a = Convert.ToInt32(sb);

                    b = Convert.ToInt32(sa);

                    ans = a + b;

                    i.Push(ans.ToString());

  

                }

                else if (c.Equals("-"))

                {

                    String sa = (String)i.Pop();

                    String sb = (String)i.Pop();

                    a = Convert.ToInt32(sb);

                    b = Convert.ToInt32(sa);

                    ans = a - b;

                    i.Push(ans.ToString());

  

                }

                else

                {

                    i.Push(v.Substring(j, 1));

                }

            }

            answer = (String)i.Pop();

        }

    }

}


Выход:

postfix evaluation: -4

Временная сложность алгоритма оценки составляет O (n), где n — количество символов во входном выражении.

Существуют следующие ограничения вышеуказанной реализации.
1) Поддерживает только 4 бинарных оператора «+», «*», «-» и «/». Его можно расширить для большего числа операторов, добавив больше вариантов переключения.
2) Допустимые операнды — это однозначные операнды. Программу можно расширить на несколько цифр, добавив разделитель, как пробел, между всеми элементами (операторами и операндами) данного выражения.

Ниже приведена расширенная программа, которая позволяет операндам иметь несколько цифр.

C ++

// Программа CPP для оценки значения постфикса
// выражение, имеющее многозначные операнды
#include <bits/stdc++.h>

using namespace std;

  
// Тип стека

class Stack 

{ 

    public:

    int top; 

    unsigned capacity; 

    int* array; 

}; 

  
// Стековые операции
Stack* createStack( unsigned capacity ) 
{ 

    Stack* stack = new Stack();

  

    if (!stack) return NULL; 

  

    stack->top = -1; 

    stack->capacity = capacity; 

    stack->array = new int[(stack->capacity * sizeof(int))]; 

  

    if (!stack->array) return NULL; 

  

    return stack; 

} 

  

int isEmpty(Stack* stack) 

{ 

    return stack->top == -1 ; 

} 

  

int peek(Stack* stack) 

{ 

    return stack->array[stack->top]; 

} 

  

int pop(Stack* stack) 

{ 

    if (!isEmpty(stack)) 

        return stack->array[stack->top--] ; 

    return '$'; 

} 

  

void push(Stack* stack,int op) 

{ 

    stack->array[++stack->top] = op; 

} 

  

  
// Основная функция, которая возвращает значение
// данного постфиксного выражения

int evaluatePostfix(char* exp) 

{ 

    // Создание стека емкости, равной размеру выражения

    Stack* stack = createStack(strlen(exp)); 

    int i; 

  

    // Посмотрим, был ли стек успешно создан

    if (!stack) return -1; 

  

    // Сканируем все символы по одному

    for (i = 0; exp[i]; ++i) 

    { 

        // если символ не заполнен, продолжаем

        if(exp[i] == ' ')continue; 

          

        // Если отсканированный символ

        // операнд (число здесь), извлечь полное число

        // Вставить его в стек.

        else if (isdigit(exp[i])) 

        { 

            int num=0; 

              

            // извлечь полный номер

            while(isdigit(exp[i])) 

            { 

            num = num * 10 + (int)(exp[i] - '0'); 

                i++; 

            } 

            i--; 

              

            // вставляем элемент в стек

            push(stack,num); 

        } 

          

        // Если отсканированный символ является оператором, выведите два

        // элементы из стека применяют оператор

        else

        { 

            int val1 = pop(stack); 

            int val2 = pop(stack); 

              

            switch (exp[i]) 

            { 

            case '+': push(stack, val2 + val1); break; 

            case '-': push(stack, val2 - val1); break; 

            case '*': push(stack, val2 * val1); break; 

            case '/': push(stack, val2/val1); break; 

              

            } 

        } 

    } 

    return pop(stack); 

} 

  
// Код драйвера

int main() 

{ 

    char exp[] = "100 200 + 2 / 5 * 7 +"; 

    cout << evaluatePostfix(exp); 

    return 0; 

} 

  
// Этот код предоставлен rathbhupendra

С

// C программа для оценки значения постфикса
// выражение, имеющее многозначные операнды
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

  
// Тип стека

struct Stack

{

    int top;

    unsigned capacity;

    int* array;

};

  
// Стековые операции

struct Stack* createStack( unsigned capacity )

{

    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));

  

    if (!stack) return NULL;

  

    stack->top = -1;

    stack->capacity = capacity;

    stack->array = (int*) malloc(stack->capacity * sizeof(int));

  

    if (!stack->array) return NULL;

  

    return stack;

}

  

int isEmpty(struct Stack* stack)

{

    return stack->top == -1 ;

}

  

int peek(struct Stack* stack)

{

    return stack->array[stack->top];

}

  

int pop(struct Stack* stack)

{

    if (!isEmpty(stack))

        return stack->array[stack->top--] ;

    return '$';

}

  

void push(struct Stack* stack,int op)

{

    stack->array[++stack->top] = op;

}

  

  
// Основная функция, которая возвращает значение
// данного постфиксного выражения

int evaluatePostfix(char* exp)

{

    // Создание стека емкости, равной размеру выражения

    struct Stack* stack = createStack(strlen(exp));

    int i;

  

    // Посмотрим, был ли стек успешно создан

    if (!stack) return -1;

  

    // Сканируем все символы по одному

    for (i = 0; exp[i]; ++i)

    {

        // если символ не заполнен, продолжаем

        if(exp[i]==' ')continue;

          

        // Если отсканированный символ

        // операнд (число здесь), извлечь полное число

        // Вставить его в стек.

        else if (isdigit(exp[i]))

        {

            int num=0;

              

            // извлечь полный номер

            while(isdigit(exp[i])) 

            {

            num=num*10 + (int)(exp[i]-'0');

                i++;

            }

            i--;

              

            // вставляем элемент в стек

            push(stack,num);

        }

          

        // Если отсканированный символ является оператором, выведите два

        // элементы из стека применяют оператор

        else

        {

            int val1 = pop(stack);

            int val2 = pop(stack);

              

            switch (exp[i])

            {

            case '+': push(stack, val2 + val1); break;

            case '-': push(stack, val2 - val1); break;

            case '*': push(stack, val2 * val1); break;

            case '/': push(stack, val2/val1); break;

              

            }

        }

    }

    return pop(stack);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    char exp[] = "100 200 + 2 / 5 * 7 +";

    printf ("%d", evaluatePostfix(exp));

    return 0;

}

  
// Этот код предоставлен Арнабом Кунду

Джава

// Java Proram для оценки значения постфикса
// выражение, имеющее многозначные операнды

import java.util.Stack;

  

class Test1

{

    // Метод для оценки значения выражения postfix

    static int evaluatePostfix(String exp)

    {

        // создаем стек

        Stack<Integer> stack = new Stack<>();

          

        // Сканируем все символы по одному

        for(int i = 0; i < exp.length(); i++)

        {

            char c = exp.charAt(i);

              

            if(c == ' ')

            continue;

              

            // Если отсканированный символ является операндом

            // (номер здесь), извлечь номер

            // Вставить его в стек.

            else if(Character.isDigit(c))

            {

                int n = 0;

                  

                // извлекаем символы и сохраняем их в num

                while(Character.isDigit(c))

                {

                    n = n*10 + (int)(c-'0');

                    i++;

                    c = exp.charAt(i);

                }

                i--;

  

                // вставляем число в стек

                stack.push(n);

            }

              

            // Если отсканированный символ является оператором, выведите два

            // элементы из стека применяют оператор

            else

            {

                int val1 = stack.pop();

                int val2 = stack.pop();

                  

                switch(c)

                {

                    case '+':

                    stack.push(val2+val1);

                    break;

                      

                    case '-':

                    stack.push(val2- val1);

                    break;

                      

                    case '/':

                    stack.push(val2/val1);

                    break;

                      

                    case '*':

                    stack.push(val2*val1);

                    break;

            }

            }

        }

        return stack.pop(); 

    }

      

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args) 

    {

        String exp = "100 200 + 2 / 5 * 7 +";

        System.out.println(evaluatePostfix(exp));

    }

}

  
// Этот код предоставлен Арнабом Кунду

C #

// C # proram для оценки значения постфикса
// выражение, имеющее многозначные операнды

using System;

using System.Collections.Generic;

  

class GFG

{
// Метод оценки стоимости
// постфиксное выражение

public static int evaluatePostfix(string exp)

{

    // создаем стек

    Stack<int> stack = new Stack<int>();

  

    // Сканируем все символы по одному

    for (int i = 0; i < exp.Length; i++)

    {

        char c = exp[i];

  

        if (c == ' ')

        {

            continue;

        }

  

        // Если отсканированный символ

        // операнд (число здесь), извлечение

        // число. Вставьте его в стек.

        else if (char.IsDigit(c))

        {

            int n = 0;

  

            // извлечь символы и

            // сохраняем в num

            while (char.IsDigit(c))

            {

                n = n * 10 + (int)(c - '0');

                i++;

                c = exp[i];

            }

            i--;

  

            // вставляем число в стек

            stack.Push(n);

        }

  

        // Если отсканированный символ

        // оператор, вытолкнуть два элемента

        // из стека применяем оператор

        else

        {

            int val1 = stack.Pop();

            int val2 = stack.Pop();

  

            switch (c)

            {

                case '+':

                stack.Push(val2 + val1);

                break;

  

                case '-':

                stack.Push(val2 - val1);

                break;

  

                case '/':

                stack.Push(val2 / val1);

                break;

  

                case '*':

                stack.Push(val2 * val1);

                break;

            }

        }

    }

    return stack.Pop();

}

  
// Код драйвера

public static void Main(string[] args)

{

    string exp = "100 200 + 2 / 5 * 7 +";

    Console.WriteLine(evaluatePostfix(exp));

}
}

  
// Этот код предоставлен Shrikant13


Выход :

757

Ссылки:
http://www.cs.nthu.edu.tw/~wkhon/ds/ds10/tutorial/tutorial2.pdf

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Стек | Набор 4 (оценка выражения Postfix)

0.00 (0%) 0 votes