postfix_evaluation.cpp File Reference

Evaluation of Postfix Expression More...

#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <string>

Include dependency graph for postfix_evaluation.cpp:

Go to the source code of this file.

Classes
class	others::postfix_expression::Stack
	Creates an array to be used as stack for storing values. More...

Namespaces
namespace	others
	for vector
namespace	postfix_expression
	Functions for Postfix Expression algorithm.

Functions
void	others::postfix_expression::push (float operand, Stack *stack)
	Pushing operand, also called the number in the array to the stack.
float	others::postfix_expression::pop (Stack *stack)
	Popping operand, also called the number from the stack.
bool	others::postfix_expression::is_number (const std::string &s)
	Checks if scanned string is a number.
void	others::postfix_expression::evaluate (float a, float b, const std::string &operation, Stack *stack)
	Evaluate answer using given last two operands from and operation.
template<std::size_t N>
float	others::postfix_expression::postfix_evaluation (std::array< std::string, N > input)
	Postfix Evaluation algorithm to compute the value from given input array.
static void	test_function_1 ()
	Test function 1 with input array {'2', '3', '1', '*', '+', '9', '-'}.
static void	test_function_2 ()
	Test function 2 with input array {'1', '2', '+', '2', '/', '5', '*', '7', '+'}.
int	main ()
	Main function.

Detailed Description

Evaluation of Postfix Expression

Author

Darshana Sarma

Create a stack to store operands (or values). Scan the given expression and do following for every scanned element. If the element is a number, push it into the stack If the element is a operator, pop operands for the operator from stack. Evaluate the operator and push the result back to the stack When the expression is ended, the number in the stack is the final answer

Definition in file postfix_evaluation.cpp.

Function Documentation

evaluate()

void others::postfix_expression::evaluate	(	float	a,
		float	b,
		const std::string &	operation,
		Stack *	stack )

Evaluate answer using given last two operands from and operation.

Parameters

a	second last added operand which will be used for evaluation
b	last added operand which will be used for evaluation
operation	to be performed with respective floats
stack	containing numbers

Returns

none

Definition at line 77 of file postfix_evaluation.cpp.

                                                                          {
    float c = 0;
    const char *op = operation.c_str();
    switch (*op) {
        case '+':
            c = a + b; // Addition of numbers
            others::postfix_expression::push(c, stack);
            break;
 
        case '-':
            c = a - b; // Subtraction of numbers
            others::postfix_expression::push(c, stack);
            break;
 
        case '*':
            c = a * b; // Multiplication of numbers
            others::postfix_expression::push(c, stack);
            break;
 
        case '/':
            c = a / b; // Division of numbers
            others::postfix_expression::push(c, stack);
            break;
 
        default:
            std::cout << "Operator not defined\n";
            break;
    }
}

is_number()

bool others::postfix_expression::is_number

(

const std::string &

s

)

Checks if scanned string is a number.

Parameters

s	scanned string

Returns

bool boolean value if string is number

Definition at line 65 of file postfix_evaluation.cpp.

                                   {
    return !s.empty() && std::all_of(s.begin(), s.end(), ::isdigit);
}

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 171 of file postfix_evaluation.cpp.

           {
    test_function_1();
    test_function_2();
 
    std::cout << "\nTest implementations passed!\n";
 
    return 0;
}

pop()

float others::postfix_expression::pop

(

Stack *

stack

)

Popping operand, also called the number from the stack.

Parameters

stack

stack containing numbers

Returns

operand float on top of stack

Definition at line 54 of file postfix_evaluation.cpp.

                        {
    float operand = stack->stack[stack->stackTop];
    stack->stackTop--;
    return operand;
}

postfix_evaluation()

template<std::size_t N>

float others::postfix_expression::postfix_evaluation

(

std::array< std::string, N >

input

)

Postfix Evaluation algorithm to compute the value from given input array.

Template Parameters

N	number of array size

Parameters

input

Array of characters consisting of numbers and operations

Returns

stack[stackTop] returns the top value from the stack

Definition at line 115 of file postfix_evaluation.cpp.

                                                       {
    Stack stack;
    int j = 0;
 
    while (j < N) {
        std::string scan = input[j];
        if (is_number(scan)) {
            push(std::stof(scan), &stack);
 
        } else {
            float op2 = pop(&stack);
            float op1 = pop(&stack);
 
            evaluate(op1, op2, scan, &stack);
        }
        j++;
    }
 
    std::cout << stack.stack[stack.stackTop] << "\n";
 
    return stack.stack[stack.stackTop];
}

push()

void others::postfix_expression::push	(	float	operand,
		Stack *	stack )

Pushing operand, also called the number in the array to the stack.

Parameters

operand	float value from the input array or evaluation
stack	stack containing numbers

Returns

none

Definition at line 44 of file postfix_evaluation.cpp.

                                       {
    stack->stackTop++;
    stack->stack[stack->stackTop] = operand;
}

test_function_1()

static void test_function_1 ( )

static

Test function 1 with input array {'2', '3', '1', '*', '+', '9', '-'}.

Returns

none

Definition at line 146 of file postfix_evaluation.cpp.

                              {
    std::array<std::string, 7> input = {"2", "3", "1", "*", "+", "9", "-"};
 
    float answer = others::postfix_expression::postfix_evaluation(input);
 
    assert(answer == -4);
}

test_function_2()

static void test_function_2 ( )

static

Test function 2 with input array {'1', '2', '+', '2', '/', '5', '*', '7', '+'}.

Returns

none

Definition at line 159 of file postfix_evaluation.cpp.

                              {
    std::array<std::string, 9> input = {"100", "200", "+", "2", "/",
                                        "5",   "*",   "7", "+"};
    float answer = others::postfix_expression::postfix_evaluation(input);
 
    assert(answer == 757);
}