ts / hs 实现后缀计算式

postfix-calc.hs

-- by @W-46ec
-- a4.hs

-- Token data type
data Token = Num Double | Op String | Err String
             deriving (Eq, Show)


-- Stack operations

-- 'dup' operator
dup :: [Token] -> [Token]
dup [] = [(Err "dup: empty stack")]
dup lst = lst ++ [last lst]

-- 'pop' operator
pop :: [Token] -> [Token]
pop [] = [(Err "pop: empty stack")]
pop (_ : xs) = xs

-- 'clear' operator
clear :: [a] -> [a]
clear lst = []

-- 'swap' operator
swap :: [Token] -> [Token]
swap [] = [(Err "swap: empty stack")]
swap [x] = [(Err "swap: not enough args")]
swap (a : (b : rest)) = (b : a : rest)


-- operators

-- 'inc' operator
inc :: [Token] -> [Token]
inc [] = [(Err "inc: empty stack")]
inc lst = let (Num x) = last lst
          in (exceptLast lst 1) ++ [(Num (x + 1))]

-- 'dec' operator
dec :: [Token] -> [Token]
dec [] = [(Err "dec: empty stack")]
dec lst = let (Num x) = last lst
          in (exceptLast lst 1) ++ [(Num (x - 1))]

-- 'sqrt' operator
sqroot :: [Token] -> [Token]
sqroot [] = [(Err "sqrt: empty stack")]
sqroot lst = let (Num x) = last lst
             in (exceptLast lst 1) ++ [(Num (sqrt x))]

-- 'sin' operator
sine :: [Token] -> [Token]
sine [] = [(Err "sin: empty stack")]
sine lst = let (Num x) = last lst
           in (exceptLast lst 1) ++ [(Num (sin x))]

-- 'cos' operator
cosine :: [Token] -> [Token]
cosine [] = [(Err "cos: empty stack")]
cosine lst = let (Num x) = last lst
             in (exceptLast lst 1) ++ [(Num (cos x))]

-- 'inv' operator
inv :: [Token] -> [Token]
inv [] = [(Err "inv: empty stack")]
inv lst = let (Num x) = last lst
          in (exceptLast lst 1) ++ [(Num (1 / x))]

-- '+' operator
plus :: [Token] -> [Token]
plus [] = [(Err "+: empty stack")]
plus lst | (length lst) <= 1 = [(Err "+: not enough args")]
plus lst = let (Num y) = last lst
               (Num x) = head (tail (reverse lst))
           in (exceptLast lst 2) ++ [(Num (x + y))]

-- '-' operator
minus :: [Token] -> [Token]
minus [] = [(Err "-: empty stack")]
minus lst | (length lst) <= 1 = [(Err "-: not enough args")]
minus lst = let (Num y) = last lst
                (Num x) = head (tail (reverse lst))
            in (exceptLast lst 2) ++ [(Num (x - y))]

-- '*' operator
multiply :: [Token] -> [Token]
multiply [] = [(Err "*: empty stack")]
multiply lst | (length lst) <= 1 = [(Err "*: not enough args")]
multiply lst = let (Num y) = last lst
                   (Num x) = head (tail (reverse lst))
               in (exceptLast lst 2) ++ [(Num (x * y))]

-- '/' operator
divide :: [Token] -> [Token]
divide [] = [(Err "/: empty stack")]
divide lst | (length lst) <= 1 = [(Err "/: not enough args")]
divide lst = let (Num y) = last lst
                 (Num x) = head (tail (reverse lst))
             in (exceptLast lst 2) ++ [(Num (x / y))]

-- '+all' operator
plusAll :: [Token] -> [Token]
plusAll [] = [(Err "+all: empty stack")]
plusAll lst = [(Num (sum (map (\(Num x) -> x) lst)))]

-- '*all' operator
timesAll :: [Token] -> [Token]
timesAll [] = [(Err "*all: empty stack")]
timesAll lst = [(Num (product (map (\(Num x) -> x) lst)))]


-- Convert from strings to functions
interpretOp :: Token -> [Token] -> [Token]
-- Unary operators
interpretOp (Op "inc") = inc
interpretOp (Op "dec") = dec
interpretOp (Op "sqrt") = sqroot
interpretOp (Op "sin") = sine
interpretOp (Op "cos") = cosine
interpretOp (Op "inv") = inv
-- Binary operators
interpretOp (Op "+") = plus
interpretOp (Op "-") = minus
interpretOp (Op "*") = multiply
interpretOp (Op "/") = divide
interpretOp (Op "+all") = plusAll
interpretOp (Op "*all") = timesAll
-- Stack operation
interpretOp (Op "dup") = dup
interpretOp (Op "pop") = pop
interpretOp (Op "clear") = clear
interpretOp (Op "swap") = swap
-- Handling unknown operator
interpretOp (Op optr) = (\x -> [(Err ("Unknown operator: " ++ optr))])

-- Evaluate an expression
evalExpr :: [Token] -> Token -> [Token]
evalExpr lst (Err msg) = [(Err msg)]
evalExpr lst op = interpretOp op lst


-- Helper functions

-- Return true if the given character is digit, otherwise return false
isDigit :: Char -> Bool
isDigit c = foldl (||) False (map (\x -> x == c) ['0'..'9'])

-- Return true if the given string is a number
isNum :: String -> Bool
isNum num = foldl (&&) True (map (\x -> x == '.' || isDigit x) num)

-- Convert a Token to a string
token2str :: Token -> String
token2str (Num x) = show x
token2str (Op s) = s

-- Convert a string to a Token
str2token :: String -> Token
str2token str | isNum str = Num (read str :: Double)
              | otherwise = Op str

-- Convert a string to a list of type Token
str2lst :: String -> [Token]
str2lst str = map str2token (words str)

-- Convert a list of type Token to a string
lst2str :: [Token] -> String
lst2str [] = ""
lst2str [(Num x)] = (show x)
lst2str [(Op str)] = str
lst2str [(Err msg)] = msg
lst2str ((Num x) : rest) = (show x) ++ " " ++ (lst2str rest)
lst2str ((Op str) : rest) = str ++ " " ++ (lst2str rest)
lst2str ((Err msg) : rest) = msg ++ " " ++ (lst2str rest)

-- Get the operator closest to the top of the stack
-- Empty list is being returned if no operator found
getFirstOp :: [Token] -> [Token]
getFirstOp [] = [(Err "empty stack")]
getFirstOp ((Op str) : _) = [(Op str)]
getFirstOp (_ : xs) = getFirstOp xs

-- Pop n elements from the stack
-- Do nothing if stack is empty
popn :: [a] -> Int -> [a]
popn lst n | n <= 0 = lst
           | (length lst) == 0 = []
           | otherwise = popn (tail lst) (n - 1)

-- Get all the numbers on top of the stack
getAllNums :: [Token] -> [Token]
getAllNums ((Num x) : xs) = (Num x) : (getAllNums xs)
getAllNums x = []

-- Return a list except the last n elements
-- Empty list is being returned if n >= the length of list
exceptLast :: [Token] -> Int -> [Token]
exceptLast lst n | (length lst) <= n = []
                 | otherwise = (head lst) : (exceptLast (tail lst) n)

-- error handler: Handle error (if any), proceed to next step if no error occur
errorHandler :: [Token] -> [Token]
errorHandler ((Err msg) : _) = [(Err msg)]   -- An error occured
errorHandler lst = lst   -- No error occur, continue

-- evaluate one expression from the stack
evalOne :: [Token] -> [Token]
evalOne lst | ((length lst) > 1) && ((length (getAllNums lst)) == (length lst))
    = [(Err ("stack: " ++ (lst2str lst) ++ ": Cannot proceed anymore"))]
evalOne lst = errorHandler (evalExpr nums op) ++ rest
              where nums = getAllNums lst
                    op = head (getFirstOp (popn lst (length nums)))
                    rest = popn lst ((length nums) + 1)

-- evaluate the whole stack as a list
evalStack :: [Token] -> [Token]
evalStack ((Err msg) : _) = [(Err msg)]
evalStack [(Num x)]   = [(Num x)]
evalStack lst = evalStack (evalOne lst)

-- evaluate the whole stack as a string
calcStack :: String -> String
calcStack str = if (length result) == 0
    then "empty stack"
    else result
    where result = lst2str (evalStack (str2lst str))

-- calc
calc :: String -> String
calc str = calcStack str


-- End of a4.hs

postfix-calc.ts

// https://www2.cs.sfu.ca/CourseCentral/383/tjd/a4.html
// 原题用 haskell 搞的
// 这里用 ts 玩一下

type Token = string | number;

function parse(str: string): Token[] {
    return str.split(' ').filter(e => e).map(e => {
        const _ = +e;
        return isNaN(_) ? e : _;
    });
}

/**
 * resolve map types
 */
interface ResolveMap {
    [op: string]: {
        len: number,
        calc: (...args: number[]) => number | number[]
    }
}

/**
 * resolve map
 */
const resolveMap: ResolveMap = {
    '+': {
        len: 2,
        calc: (a: number, b: number) => a + b
    },
    '-': {
        len: 2,
        calc: (a: number, b: number) => a - b
    },
    '*': {
        len: 2,
        calc: (a: number, b: number) => a * b
    },
    '/': {
        len: 2,
        calc: (a: number, b: number) => a / b
    },
    'sqrt': {
        len: 1,
        calc: (a: number) => Math.sqrt(a)
    },
    'dup': {
        len: 1,
        calc: (a: number) => [a, a]
    },
    '+all': {
        len: +Infinity,
        calc: (...args: number[]) => args.reduce((a, b) => a + b)
    },
    '*all': {
        len: +Infinity,
        calc: (...args: number[]) => args.reduce((a, b) => a * b)
    },
    'clear': {
        len: +Infinity,
        calc: () => []
    },
    'pop': {
        len: +Infinity,
        calc: (...args: number[]) => args.slice(0, -1)
    },
    'inc': {
        len: 1,
        calc: (a: number) => a + 1
    },
    'dec': {
        len: 1,
        calc: (a: number) => a - 1
    },
    'sin': {
        len: 1,
        calc: (a: number) => Math.sin(a)
    },
    'cos': {
        len: 1,
        calc: (a: number) => Math.cos(a)
    }
}

function calc(chars: Token[], ...args: number[]): number {
    // console.log(chars, args);
    if (chars.length === 0) {
        if (args.length) {
            return args[0]
        } else {
            throw new Error('empty stack');
        }
    } else {
        const first = chars[0];

        if (typeof first === 'number') {
            return calc(chars.slice(1), ...args, first);
        } else {
            const op = resolveMap[first];

            if (!op) {
                throw new Error('Operator Not Found: ' + first);
            }

            // 倒数 n 个哦
            const __ = args.slice(-op.len);

            if ((__.length !== op.len) && op.len !== Infinity) {
                throw new Error(`${first}: not enough args, received: [ ${__.join(', ')} ]`);
            }

            const val = op.calc(...__);

            const restArgs = args.slice(0, -op.len);

            if (typeof val === 'number') {
                return calc(chars.slice(1), ...restArgs, val);
            } else {
                // ... en 
                return calc(chars.slice(1), ...restArgs, ...val);
            }
        }
    }
}

/**
 * 包一层
 */
const $ =  (s: string) => {
    try {
        console.log('> calc "' + s + '"');
        console.log(calc(parse(s)));
    } catch (e) {
        console.log(e.message);
    }

    console.log('');
}

$('1 2 + 3 *');
$('1 2 3 * +');
$('2 sqrt 3 sqrt +');
$('11 dup *');
$('0 5 /');
$('5 0 /');
$('2 3 + 4 2 +all');
$('2 3 + 4 2 *all')
$('2 3 + 4 2 clear');
$('2 3 inc * pop');
$('3.2 sin dup * 3.2 cos dup * +')
$('2 +');
$('dec')