Algorithm Homework Weekly - 6

There’s only one problem for this week since all other homework is about to kill me. And this week I solve a simple parser problem. The basic calculator, here’s the problem.

Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2

" 2-1 + 2 " = 3

"(1+(4+5+2)-3)+(6+8)" = 23

My accepted code can be found here

A more engineering approach of this problem would be first construct a tree for expression from the input string, and evaluate the expression tree (AST) for the answer. This problem is simplified a lot, we don’t need to support any operator precedence or error handling which would be mentioned a little in the article. Here we don’t need any engineering method, and just do a linear scan over the string and add a little bit recursion to handle the parenthesis.

The algorithm is simple enough, assume spaces are properly skipped

let n: int = 0;
let s: string = input;
Calculate():
    let acc = 0
    if NextChar() == '('
    then ++n; acc = Calculate()
    else acc = Number()

    loop:
        if EndOfString() then return acc
        if NextChar() == ')' then ++n; return acc

        let operator = Operator()
        let next = 0
        if NextChar() == '(' then ++n; next = Calculate()
        else next = Number()

        acc = operator(acc, next)

NextChar(): return s[n]
EndOfString(): return n == length(s)

Operator():
    let c = NextChar()
    ++n
    return if c == '+' then (+) else (-)

Number():
    let acc = 0
    for isDigit(NextChar())
        acc = acc * 10 + NextChar() - '0'
        ++n
    return acc

Since we assume the input is always valid, so we know a expression always starts with a left parenthesis or a number, a number(expression) is always followed by end of string, right parenthesis or an operator. An operator is always + or -.

So error handling is simple here, we know all expected cases, then we know all unexpected cases. So when character unexpected appears(a number followed by left parenthesis), an error occurs and parsing abort.

If the problem add operator precedence(* and / and ^ etc.), I would prefer using operator precedence parsing, and we’re all done.

Last

There are too many things to be done lately, so not much time for sitting in front of my laptop and thinking algorithm problem solutions for an entire afternoon.

I gotta go to do my next homework bye :D