postfix_evaluation.cpp File Reference

Evaluation of Postfix Expression More...

#include <algorithm>
#include <cassert>
#include <iostream>
#include <stack>
#include <string>
#include <vector>

Include dependency graph for postfix_evaluation.cpp:

Go to the source code of this file.

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

Functions
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, std::stack< float > &stack)
	Evaluate answer using given last two operands from and operation.
float	others::postfix_expression::postfix_evaluation (const std::vector< std::string > &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 {'100', '200', '+', '2', '/', '5', '*', '7', '+'}.
static void	test_function_3 ()
static void	test_single_input ()
static void	test_not_enough_operands ()
static void	test_not_enough_operands_empty_input ()
static void	test_too_many_operands ()
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,
		std::stack< float > &	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 49 of file postfix_evaluation.cpp.

                                      {
    float c = 0;
    const char *op = operation.c_str();
    switch (*op) {
        case '+':
            c = a + b;  // Addition of numbers
            stack.push(c);
            break;
 
        case '-':
            c = a - b;  // Subtraction of numbers
            stack.push(c);
            break;
 
        case '*':
            c = a * b;  // Multiplication of numbers
            stack.push(c);
            break;
 
        case '/':
            c = a / b;  // Division of numbers
            stack.push(c);
            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 37 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 202 of file postfix_evaluation.cpp.

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

postfix_evaluation()

float others::postfix_expression::postfix_evaluation

(

const std::vector< std::string > &

input

)

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

Parameters

input

vector of strings consisting of numbers and operations

Returns

stack[stackTop] returns the top value from the stack

Definition at line 97 of file postfix_evaluation.cpp.

                                                            {
    std::stack<float> stack;
 
    for (const auto &scan : input) {
        if (is_number(scan)) {
            stack.push(std::stof(scan));
 
        } else {
            const auto op2 = remove_from_stack(stack);
            const auto op1 = remove_from_stack(stack);
 
            evaluate(op1, op2, scan, stack);
        }
    }
 
    const auto res = remove_from_stack(stack);
    if (!stack.empty()) {
        throw std::invalid_argument("Too many operands");
    }
    return res;
}

test_function_1()

void test_function_1 ( )

static

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

Returns

none

Definition at line 126 of file postfix_evaluation.cpp.

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

test_function_2()

void test_function_2 ( )

static

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

Returns

none

Definition at line 139 of file postfix_evaluation.cpp.

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

test_function_3()

void test_function_3 ( )

static

Definition at line 147 of file postfix_evaluation.cpp.

                              {
    std::vector<std::string> input = {
        "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1",
        "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1",
        "+", "+", "+", "+", "+", "+", "+", "+", "+", "+", "+",
        "+", "+", "+", "+", "+", "+", "+", "+", "+", "+"};
    float answer = others::postfix_expression::postfix_evaluation(input);
 
    assert(answer == 22);
}

test_not_enough_operands()

void test_not_enough_operands ( )

static

Definition at line 165 of file postfix_evaluation.cpp.

                                       {
    std::vector<std::string> input = {"+"};
    bool throws = false;
    try {
        others::postfix_expression::postfix_evaluation(input);
    } catch (std::invalid_argument &) {
        throws = true;
    }
    assert(throws);
}

test_not_enough_operands_empty_input()

void test_not_enough_operands_empty_input ( )

static

Definition at line 176 of file postfix_evaluation.cpp.

                                                   {
    std::vector<std::string> input = {};
    bool throws = false;
    try {
        others::postfix_expression::postfix_evaluation(input);
    } catch (std::invalid_argument &) {
        throws = true;
    }
    assert(throws);
}

test_single_input()

void test_single_input ( )

static

Definition at line 158 of file postfix_evaluation.cpp.

                                {
    std::vector<std::string> input = {"1"};
    float answer = others::postfix_expression::postfix_evaluation(input);
 
    assert(answer == 1);
}

test_too_many_operands()

void test_too_many_operands ( )

static

Definition at line 187 of file postfix_evaluation.cpp.

                                     {
    std::vector<std::string> input = {"1", "2"};
    bool throws = false;
    try {
        others::postfix_expression::postfix_evaluation(input);
    } catch (std::invalid_argument &) {
        throws = true;
    }
    assert(throws);
}