Integer Calculator with Postfix Notation

A C++ console application that evaluates mathematical expressions using postfix (Reverse Polish Notation) conversion and stack-based evaluation.

Overview

This calculator converts infix notation expressions to postfix notation and evaluates them step-by-step, displaying the intermediate steps. It supports basic arithmetic operators, functions, and parentheses with proper precedence handling.

Features

• Arithmetic Operators: +, -, *, / (integer division)
• Functions:
  • IF(a, b, c) - returns b if a > 0, otherwise c
  • N(a) - unary negation (returns -a)
  • MIN(a1, a2, ...) - minimum of any number of arguments
  • MAX(a1, a2, ...) - maximum of any number of arguments
• Parentheses for grouping expressions
• Operator Precedence:
  1. Parentheses ( )
  2. Functions: MIN, MAX, N, IF
  3. Multiplication and Division: *, /
  4. Addition and Subtraction: +, -

Project Structure

├── app.cpp          # Main application logic and expression parsing
├── Token.h/cpp      # Base token class and factory methods
├── Number.h         # Number token implementation
├── Operation.h      # Operator token implementation (+, -, *, /)
├── Function.h       # Function token implementation (IF, N, MIN, MAX)
└── Stack.h/cpp      # Custom stack implementation

Input Format

n
expression1 .
expression2 .
...
expressionN .

• n - number of expressions to evaluate
• Each expression is in infix notation with tokens separated by whitespace
• Each expression must end with a dot (.)
• All operands are positive integers (results may be negative)
• Function names are uppercase letters only

Output Format

For each expression:

1. The expression in postfix notation
2. Step-by-step evaluation showing:
   • The operator/function being applied
   • The current stack contents
3. The final result
4. If division by zero occurs, prints ERROR and moves to next expression

Note: MIN and MAX functions display their argument count in postfix notation (e.g., MIN3, MAX4)

Example

Input:

4
MIN ( 100 , MAX ( 1 , 34 , 2 ) , 80 ,  MIN ( 66 , 36  , 35 , 77 ) , 50 , 60 ) .
2 + MIN ( 100 , MAX ( 1 , 6 * 5 + 2 , 2 ) , 80 ,  MIN ( 66 , 36  , 35 , 77 ) , 50 , 60 ) * 3 .
N 400 + ( 11 - ( 3 * 2 ) ) / 2 + N N 200 .
IF ( ( 6 + 8 ) , ( 4 / 2 ) , MIN ( 8 , 2 , 1 , 0 , 3 ) ) * 2 * 6 / N ( 3 ) .

Output:

100 1 34 2 MAX3 80 66 36 35 77 MIN4 50 60 MIN6
MAX3 2 34 1 100
MIN4 77 35 36 66 80 34 100
MIN6 60 50 35 80 34 100
34

2 100 1 6 5 * 2 + 2 MAX3 80 66 36 35 77 MIN4 50 60 MIN6 3 * +
* 5 6 1 100 2
+ 2 30 1 100 2
MAX3 2 32 1 100 2
MIN4 77 35 36 66 80 32 100 2
MIN6 60 50 35 80 32 100 2
* 3 32 2
+ 96 2
98

400 N 11 3 2 * - 2 / + 200 N N +
N 400
* 2 3 11 -400
- 6 11 -400
/ 2 5 -400
+ 2 -400
N 200 -398
N -200 -398
+ 200 -398
-198

6 8 + 4 2 / 8 2 1 0 3 MIN5 IF 2 * 6 * 3 N /
+ 8 6
/ 2 4 14
MIN5 3 0 1 2 8 2 14
IF 0 2 14
* 2 2
* 6 4
N 3 24
/ -3 24
-8

Key Implementation Details

Infix to Postfix Conversion

Uses the Shunting Yard Algorithm:

• Numbers are immediately added to the output
• Operators are pushed to the operator stack based on precedence
• Functions are treated as high-precedence operators
• Parentheses enforce grouping
• Commas in function arguments trigger argument counting

Stack-Based Evaluation

• Numbers are pushed onto the evaluation stack
• When an operator/function is encountered:
  • Required operands are popped from the stack
  • The operation is performed
  • The result is pushed back onto the stack

Error Handling

• Division by zero is detected during evaluation
• Prints ERROR and skips to the next expression

Building and Running

# Compile (example using g++)
g++ -o calculator app.cpp token.cpp stack.cpp -std=c++11

# Run
./calculator < input.txt

Technical Notes

• All arithmetic operations use integer division (C++ / operator)
• Values are assumed to fit within the int range
• The stack implementation uses a custom linked-list structure
• Memory management uses manual allocation/deallocation
• Token polymorphism allows unified handling of different token types

Class Hierarchy

Token (abstract base)
├── Number
└── Operation
    └── Function

Each token type implements:

• Print() - for output display
• Apply() - for evaluation (operations only)
• GetType() - for token classification
• Type-specific accessors

Algorithm Complexity

• Time Complexity: O(n) where n is the number of tokens in the expression
• Space Complexity: O(n) for the stacks used during conversion and evaluation

Limitations

• No support for floating-point numbers
• Division by zero causes error and skips to next expression
• Input must be well-formed (no syntax validation beyond basic parsing)
• Function names must be exactly as specified (case-sensitive)