A sophisticated calculator implementation with string manipulation and expression evaluation capabilities
🎓 Final Project for Data Structures and Algorithms Course
👨🏫 Under The Supervision of Prof. Hamid Hoorfar
🍂 Fall 2020 Semester
This project implements an advanced calculator machine that processes mathematical expressions through efficient string manipulation and evaluation. The calculator maintains an input string with a movable cursor and supports various operations for building and evaluating mathematical expressions.
- 📝 String Manipulation: Dynamic cursor movement, character insertion, and deletion capabilities
- 🧠 Expression Evaluation: Robust evaluation of mathematical expressions with operator precedence
- ⚡ Postfix Conversion: Internal conversion to Reverse Polish Notation for efficient computation
- 💾 Result Caching: Smart caching mechanism for previously computed expressions
- 🏗️ Optimized Data Structures: Efficient implementation using linked lists and stacks
- ⏱️ Performance Optimized: Meets strict time (1s) and memory (256MB) constraints
The calculator supports the following interactive commands:
| Command | Description | Example |
|---|---|---|
← (<) |
Move cursor one position left | "12|3" → "1|23" |
→ (>) |
Move cursor one position right | "1|23" → "12|3" |
c + |
Insert character c at cursor position |
"12|3" + 4 → "124|3" |
- |
Delete character before cursor | "12|3" → "1|3" |
? |
Display current string with cursor position | Shows "12|3" |
! |
Evaluate expression and display result | "12+3" → 15 |
Input String → [Parser] → [Postfix Converter] → [Evaluator] → Result
↑ ↑ ↑
[Cursor Manager] [Operator Stack] [Operand Stack]- 🔗 Linked List: For efficient string manipulation and cursor operations
- 📚 Stack: For expression parsing and evaluation (both operator and operand stacks)
- 🗃️ Cache: For storing previously computed results
- String Representation: Uses a doubly linked list for O(1) insertion/deletion at cursor position
- Expression Parsing: Implements Shunting-yard algorithm for infix-to-postfix conversion
- Evaluation: Uses stack-based postfix evaluation with proper operator precedence
- Caching: Memoization technique to avoid redundant computations
- ⏰ Time Limit: 1 second per operation
- 💾 Memory Limit: 256 MB total usage
- 📊 Complexity: O(n) for most operations, optimized for large inputs
>> 1+2+3?
>> 4+<!
>> <5+!>> 1+2+3|
>> 6
>> 65
>> 1+2+35|- C++ Compiler (GCC, Clang, or MSVC)
- C++11 or higher support
g++ -std=c++11 -O2 main.cpp -o calculator./calculatorCalculator/
├── Calculator.cpp # Main program entry point
└── README.md # This file📄 This project is licensed under the MIT License - see the LICENSE file for details.