Kotlin Programming 2020 Spring - Midterm Project Hints
===
###### tags: `Kotlin`

## Input Processing

### Task 1

Write a function `addSpace(expr: String): String` to add some spaces between brackets, operators, and operands in `expr`. That is, the return value of `addSpace("123+678*(9+10)")` can be `"123 + 678 * ( 9 + 10 ) "` or any other string with spaces between brackets, operators, and operands.

Hint: use `String.replace()`

### Task 2

Write a function `toTokens(str: String): List<String>` that splits `str` by spaces. That is, the return value of `toToken(" 123 45 678 9 0")` equals `listOf("123", "45", "678", "9", "0")`.

Hint: use `filter`

## Evaluation Algorithm

### Naive Approach

Idea: Use a `MutableList<Any>` to maintain the expression. Keep finding out what is the next operation to be carried out. Apply the operation and repeat the previous steps until there is no application to be carried out.

#### `is` operator

In the `MutableList<Any>`, we use `Double` to store the numbers and use `String` or `Char` to store the operators and brackets. We can use `is` operator to determine whether a value is `Double` or `String`.

fun main() {
    var toks = listOf("(","1","+","2",")","*","3","+","4")
    var mList = mutableListOf<Any>()
    for (tok in toks) {
        if ("()+-*/".contains(tok)) {
            mList.add(tok)
        }
        else {
            mList.add(tok.toDouble())
        }
    }
    for (v in mList) {
        if (v is String && "+-*/".contains(v)) {
            println("$v is an operator.")
        } else if (v is Double) {
            println("$v is a number.")        
        } else {
            println("$v is a bracket.")
        }
    }
}

#### Task 1

Find the next operation:
1. If there are operators in the deepest brackets, then the next operation is to evaluate operator with the highest priority.
2. Otherwise, there must be exact one number. The next operation is to remove the brackets.

If you cannot find the next operation, then the `MutableList<Any>` must contain exactly one number, which is the answer. Otherwise, the expression is not valid.

#### Task 2

Apply the operation to modify the `MutableList<Any>`.

### Divide and Conquer Approach

Sample solution use this approach. Use a `List<String>` to maintain the expression. If the number of elements in the list is one, then convert to `Double` and return the result. Otherwise, find out the last operation (either an operator or a pair of bracket). If it is an operator, we evaluate its two operands recursively and then apply it to the results. If it is a pair of brackets, we just remove the brackets; then we evaluate the result.

### Task 1

Write the conversion codes for one element case.

### Task 2

Write codes for finding the last operation.

### Task 3

Evaluate the result by recursive calls.

### [Shuting-yard Algorithm](https://en.wikipedia.org/wiki/Shunting-yard_algorithm)

If you major in Computer Science, then you should have known this already. But, you have to do extra things to pass the test cases.