# Homework3

[Homework 3 is due on Jul 12 (Tue) at 11:59pm]

## Problem:

“A simple calculator for single-digit integers”

Evaluate expressions that are presented in Infix notation. Assume that there are no parentheses or spaces in the expression.

The supported operations are:

(2) subtraction (‘-‘),

(3) multiplication (‘*’),

(4) division (‘/’), and

(5) exponentiation (‘^’).

For example, let’s say, you have an expression:

5-3*6+2^3

The expected output is: -5

Since it is easier for the computer to operate on a prefix or postfix notation, you can take a two-stage approach to solve this problem:

Stage 1: Convert the expression from infix to postfix.

The postfix notation for the above example would be: 536*-23^+

Stage 2: Evaluate the expression in the postfix form.

## Algorithm for Stage 1: InfixToPostfix

(using a stack to hold the operators and output the result into another string)

1. Process each character in the input string (containing the infix expression) one by one.

2. If current character is a digit, output it immediately.

3. Otherwise (if it is an operator),

4. (a) While the stack is not empty and the operator has a precedence lower than or equal to the top element of the stack, pop the top element of the stack and output it.

4. (b) Push the operator into the stack.

5. After processing all the characters in the input, remove the remaining operators in the stack and output them in sequence.

## Algorithm for Stage 2: EvaluatePostfix

(taking the output string generated by Stage 1 and using another stack)

1. Process each character in the Postfix string.

2. If it is a number, push it into the stack.

3. If it is an operator, pop the stack twice for the two operands. Perform the operation on these operands, and push the result into the stack.

4. When you have exhausted the Postfix string, pop the stack to output the result of the evaluated expression.

## Notes:

1. Please note that chars can be interchangeably used with ints. So, the same stack implementation without any change can be leveraged.

2. You can process a string with a for loop running through the length of the string (using the function length()).

3. You can use the string concatenation operator ‘+’ for generating the postfix string.

4. The right associativity of power-of (^) operator can be handled by considering ^ to have a higher precedence over  a preceding ^ operator. E.g. 2^3^2 should evaluate to 512 (or 2^(3^2)) and not 64. To help you resolve this, you have been already provided with the calculator::hasHigherPrecedenceThan() function.

5. On the other hand, we want division to be left associative. In other words 2/3/2 should resolve to (2/3)/2 while 2^3^2 resolves to 2^(3^2).

6. If calculator::isOperator() returns false, it can be assumed to be a digit. In other words, this assignment does not emphasize on checking for illegal characters.

7. You are responsible for populating only two functions:

```void calculator::convertInputIntoPostfix()
void calculator::evaluatePostfixIntoResult()```

## Starter files:

Here are the starter files. The stopping character is “.”. When the stopping character is encountered, the calculator exits.

## Expected Output:

2+3*3*3

Postfix = 233*3*+

Result = 29

2-9/3/3

Postfix = 293/3/-

Result = 1

2+2^3^2

Postfix = 2232^^+

Result = 514

4-5+8

Postfix = 45-8+

Result = 7

5-3*6+2^3

Postfix = 536*-23^+

Result = -5

4-5+2*4*5-2-8+3^2^2

Postfix = 45-24*5*+2-8-322^^+

Result = 110

4-10/2/1+6/3+8/2/2+9/2/2/1

Postfix = 4102/1/-63/+82/2/+92/2/1/+

Malformed expression

Result = 7

4-6/2/1+6/3+8/2/2+9/2/2/1

Postfix = 462/1/-63/+82/2/+92/2/1/+

Result = 7

9/2/2/1

Postfix = 92/2/1/

Result = 2

8/2/2

Postfix = 82/2/

Result = 2

.

## Solution:

The solution files are here.