The purpose of this project is to create a calculator that deviates from the standard approach commonly found, where arithmetic operators are applied sequentially (taking the result of the previous calculation and performing the next operation).
This project aims to build a calculator that can evaluate numerical expressions entered by the user through a graphical interface, providing the result or error messages when applicable. To achieve this, the method developed by Polish mathematician Jan Łukasiewicz was used, which evaluates expressions without the need to worry about operation priorities. This method includes the following three concepts:
- Infix: Operator is placed between operands (e.g.,
4 - 3). - Prefix: Operator precedes the operands (e.g.,
- 4 3). - Postfix: Operator follows the operands (e.g.,
4 3 -).
This implementation uses queues, stacks, and linked lists (though the latter is not strictly necessary). The technique involves converting the user's input expression (in infix notation) to postfix notation (storing elements in a stack and moving them to a queue according to the rules outlined in Rules), and then calculating the value of the expression from the queue.
To ensure calculations are performed correctly, inputs must follow the correct syntax. The operators and their precedence levels align with those commonly used in programming and mathematics.
| Symbol | Meaning |
|---|---|
| + | Addition |
| - | Subtraction |
| * | Multiplication |
| / | Division |
| ^ | Exponentiation |
| () | Parentheses |
| Symbol | Meaning | Precedence |
|---|---|---|
| () | Parentheses |
|
| ^ | Exponentiation | |
| * | Multiplication | |
| / | Division | |
| + | Addition | |
| - | Subtraction |
To convert an infix expression to postfix, specific rules must be followed. One important case involves evaluating the operators in the sequence of the expression compared to the top of the stack. The table below indicates whether the current operator should be pushed onto the stack or whether the top of the stack should be popped into the queue before inserting the new operator.
| Operator at Stack Top | Operator from Sequence | ||||||
|---|---|---|---|---|---|---|---|
| ( | ^ | * | / | + | - | ) | |
| ( | F | F | F | F | F | F | T |
| ^ | F | F | T | T | T | T | T |
| * | F | F | T | T | T | T | T |
| / | F | F | T | T | T | T | T |
| + | F | F | F | F | T | T | T |
| - | F | F | F | F | T | T | T |
| ) | F | F | F | F | F | F | F |
Some rules for moving elements between the operator stack and the output queue are as follows:
- If the current token is
(, push it onto the operator stack. - If the current token is a number, enqueue it into the output queue.
- If the current token is an operator (
+,-,*,/,^):- Check whether any operators should be removed from the stack, using the table above as a guide:
- If the table value is
T(true), pop the stack and enqueue the element. - If the value is
F(false), skip popping and proceed to the next step. - Repeat until the top of the stack evaluates to
F.
- If the table value is
- Push the current operator onto the stack.
- Check whether any operators should be removed from the stack, using the table above as a guide:
- If the current token is
), pop elements from the stack and enqueue them until encountering(, which should be discarded.
The process ends when the stack is empty, and all elements are in the output queue (excluding parentheses).
Input: 1 + 2 * (3 - 1)
Postfix expression in the output queue: ['1', '2', '3', '1', '-', '*', '+']
In this step, you will need two variables, such as "v1" and "v2", to store the numerical values of the current operation, and to store the operator, you will need to create a variable like "op".
To remove an element from the output queue, you must verify and follow the following rules:
-
If the element is a numerical value, push it onto the Result Stack. Repeat this step until the element removed from the Output Queue is an operator.
-
If the element removed from the Output Queue is an operator, store it in the char variable defined as
op.- Don't stop there... When encountering a logical operator and after storing it in
op, pop one element (which must be a numeric string), convert it to a number, and store it inv2. Then, pop another element (which must also be a numeric string), convert it to a number, and store it inv1. Next, calculate the result of the expression:v1 op v2. This result should be stored in the Result Stack.
- Don't stop there... When encountering a logical operator and after storing it in
-
Done! If there are still elements in the Output Queue, you must apply the general rule again (return to step 3.2). If there are no elements left in the Output Queue, there should be a single element in the Result Stack, which will be the final result of the expression.
-
At the end of step 3, you will have the final result of the expression, which is the expected output of the program. See the application of these steps below for the example:
The final result is always the single element in the stack, considering that the queue is empty and there are no operations in progress.
- Clone the repository:
git clone https://github.com/ODCS1/Expression-Calculator.git - Change Directory:
cd Expression-Calculator - Install dependencies:
mvn install
- Run the application:
In the IDE, run the file
MainApp.java.
Or, build the application to generate the .jar file, navigate to the folder where the .jar file was generated, and execute:
java -jar Expression-Calculator.jar
Made with contrib.rocks.