parsing math expression

ExpressionParser.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CalHomework
{

    /// <summary>
    /// Everything according to my blog:
    /// https://vincentdchan.github.io/2016/07/parse-math-expression/
    /// </summary>
    class ExpresssionParser
    {
        Dictionary<char, int> OperatorsPrecedence = new Dictionary<char, int>()
        {
            {'+', 1},
            {'-', 1},
            {'*', 2},
            {'/', 2},
        };

        private Stack<int> valueStack = new Stack<int>();
        private Stack<char> operatorStack = new Stack<char>();

        private string content;
        private int ptr = 0;

        public int Parse(string _content)
        {
            content = _content;
            return Parse();
        }

        private bool isDigit(char ch)
        {
            return ch >= '0' && ch <= '9';
        }

        private bool isOp(char ch)
        {
            return ch == '+' || ch == '-' || ch == '*' || ch == '/';
        }

        private string readToken()
        {
            StringBuilder sb = new StringBuilder();
            if (!isDigit(content[ptr]))
            {
                throw new ParseException();
            }
            char ch;
            while (ptr < content.Length && isDigit(ch = content[ptr]))
            {
                sb.Append(ch);
                ptr++;
            }
            return sb.ToString();
        }

        private void reduce()
        {
            var a = valueStack.Pop();
            var b = valueStack.Pop();
            var _op = operatorStack.Pop();
            valueStack.Push(reduce(a, b, _op));
        }

        private char readOperator()
        {
            StringBuilder sb = new StringBuilder();
            if (!isOp(content[ptr]))
            {
                throw new ParseException();
            }
            else
            {
                return content[ptr++];
            }
        }

        private int reduce(int a, int b, char op)
        {
            switch(op)
            {
                case '+':
                    return a + b;
                case '-':
                    return a - b;
                case '*':
                    return a * b;
                case '/':
                    return a / b;
                default:
                    throw new ParseException();
            }
        }

        private bool isFinished()
        {
            return ptr < content.Length;
        }

        private int Parse()
        {
            // init
            valueStack.Push(int.Parse(readToken()));

            while (isFinished())
            {
                var op = readOperator();
                if (operatorStack.Count == 0)
                {
                    operatorStack.Push(op);
                    valueStack.Push(int.Parse(readToken()));
                }
                else
                {
                    bool isReduced = false;
                    while (operatorStack.Count > 0)
                    {
                        var opTop = operatorStack.Peek();
                        if (OperatorsPrecedence[op] > OperatorsPrecedence[opTop])
                        {
                            operatorStack.Push(op);
                            valueStack.Push(int.Parse(readToken()));
                            isReduced = false;
                            break;
                        } else
                        {
                            reduce();
                            isReduced = true;
                        }
                    }

                    if (isReduced)
                    {
                        ptr--;
                    }
                }
            }

            // reduce until finished

            while (valueStack.Count > 1)
            {
                reduce();
            }

            return valueStack.Peek();
        }

    }

    class ParseException : Exception
    {

    }

}

main.hs

import Data.Char

data Token = Num Int 
    | T_Plus | T_Sub 
    | T_Mul | T_Div
    deriving (Show)

getPrecedence:: Token -> Int
getPrecedence T_Plus = 1
getPrecedence T_Sub = 1
getPrecedence T_Mul = 2
getPrecedence T_Div = 2

evalOp :: Token -> Int -> Int -> Int
evalOp T_Plus a b = a + b
evalOp T_Sub a b = a - b
evalOp T_Mul a b = a * b
evalOp T_Div a b = a `div` b

tokenizer:: String -> [Token]
tokenizer expr = reverse (_tokenizer expr [] [])

_tokenizer:: String -> String -> [Token] -> [Token]
_tokenizer "" [] previous = previous
_tokenizer "" buf previous = ((Num $ read $ reverse buf):previous)
_tokenizer (ch:expr) buf previous = 
    if (Data.Char.isDigit ch) then
        _tokenizer expr (ch:buf) previous
    else
        case buf of 
            [] -> 
                case ch of
                    '+' -> _tokenizer expr [] (T_Plus:previous)
                    '-' -> _tokenizer expr [] (T_Sub:previous)
                    '*' -> _tokenizer expr [] (T_Mul:previous)
                    '/' -> _tokenizer expr [] (T_Div:previous)
            _ -> _tokenizer (ch:expr) [] ((Num $ read $ reverse buf):previous)

eval :: [Token] -> Int
eval ((Num value):tokens) = _eval tokens [value] []

_eval :: [Token] -> [Int] -> [Token] -> Int
_eval [] [value] _ = value
_eval (op:(Num num):tokens) numStack [] =
    _eval tokens (num:numStack) [op]
_eval (op:(Num num):tokens) numStack (topOp:opStack) =
    if (getPrecedence op) > (getPrecedence topOp) then
        _eval tokens (num:numStack) (op:topOp:opStack)
    else
        case numStack of
            (num1:num2:stack) ->
                _eval (op:(Num num):tokens) ((evalOp topOp num1 num2):stack) opStack
_eval [] (num1:num2:numStack) (topOp:opStack) =
    _eval [] ((evalOp topOp num1 num2):numStack) opStack

main.ml

type token = Num of int 
    | T_Plus | T_Sub
    | T_Mul | T_Div

let showToken tok = 
    match tok with
        Num(num) -> "num"
        | T_Plus -> "T_Plus"
        | T_Sub -> "T_Sub"
        | T_Mul -> "T_Mul"
        | T_Div -> "T_Div"

let getPrecedence tok =
    match tok with
        T_Plus -> 1
        | T_Sub -> 1
        | T_Mul -> 2
        | T_Div -> 2

let isDigit ch =
    let ascii_code = Char.code ch in
    let ascii_0 = Char.code '0' in
    let ascii_9 = Char.code '9' in
    ascii_code >= ascii_0 && ascii_code <= ascii_9

let rec _tokenizer input buffer readToken =
    let str_length = String.length input in
    let buffer_length = String.length buffer in
        if str_length = 0 then
            if buffer_length = 0 then
                readToken
            else
                (Num (Pervasives.int_of_string buffer))::readToken
        else
            let first_char = String.get input 0 in
            let tail = String.sub input 1 (str_length - 1) in
                if isDigit first_char then
                    _tokenizer tail (buffer ^ (String.make 1 first_char)) readToken
                else
                    if buffer_length = 0 then
                        match first_char with
                            '+' -> _tokenizer tail "" (T_Plus::readToken)
                            | '-' -> _tokenizer tail "" (T_Sub::readToken)
                            | '*' -> _tokenizer tail "" (T_Mul::readToken)
                            | '/' -> _tokenizer tail "" (T_Div::readToken)
                    else 
                        _tokenizer input "" ((Num (Pervasives.int_of_string buffer))::readToken)

let tokenizer input = List.rev (_tokenizer input "" [])

let evalOp op a b = 
    match op with
        T_Plus -> a + b
        | T_Sub -> a - b
        | T_Mul -> a * b
        | T_Div -> a / b
        | _ -> 0

let rec _eval tokens numStack opStack =
    match tokens with
        [] ->
            (match numStack with
                [value] -> value
                | num1::num2::ns ->
                    let topOp = List.hd opStack in
                    let result = evalOp topOp num1 num2 in
                    _eval [] (result::ns) (List.tl opStack))
        | op::(Num num)::tks ->
            if (List.length opStack) = 0 then
                _eval tks (num::numStack) [op]
            else
                let topOp = List.hd opStack in
                let opTl = List.tl opStack in
                if (getPrecedence op) > (getPrecedence topOp) then  (* shift *)
                    _eval tks (num::numStack) (op::opStack)
                else    (* reduce *)
                    (match numStack with
                        num1::num2::ft ->
                            _eval tokens ((evalOp topOp num1 num2)::ft) (opTl)
                    )
        | (Num num)::tks ->
            _eval tks (num::numStack) opStack

let eval tokens = _eval tokens [] []

使用 parsec 来实现解析数学表达式，更能体现函数式的抽象能力和优雅所在。