#!/bin/bash

die () {
    echo "$*" >&2
    exit 1
}

or () {
    [[ $1 != *(0) ]]
    REPLY=${@:1+$?:1}
}
and () {
    [[ $1$2 != *(0) ]] && REPLY=$1 || REPLY=0
}

declare -A ops
ops=(
    [lt]=\< [gt]=\>
    [eq]=== [ne]=!=
)
for op in "${!ops[@]}"; do
    eval "$op"' () {
        if [[ $1$2 = *([0-9]) ]]; then
            REPLY=$(( $1 '"${ops[$op]}"' $2 ))
        else
            [[ $1 '"${ops[$op]}"' $2 ]]; REPLY=$?
        fi
    }'
done

ops=(
    [le]=\< [ge]=\>
)
for op in "${!ops[@]}"; do
    eval "$op"' () {
        if [[ $1$2 = *([0-9]) ]]; then
            REPLY=$(( $1 == $2 || $1 '"${ops[$op]}"' $2 ))
        else
            [[ $1 == $2 || $1 '"${ops[$op]}"' $2 ]]; REPLY=$?
        fi
    }'
done

ops=(
    [add]=+ [sub]=-
    [mul]=* [div]=/ [mod]=%
)
for op in "${!ops[@]}"; do
    eval "$op"' () {
        evaluate "$2"
        tmp2=$REPLY
        evaluate "$1"
        tmp1=$REPLY
        [[ $tmp1$tmp2 = *([0-9]) ]] || die non-integer argument
        REPLY=$(( $tmp1 '"${ops[$op]}"' $tmp2 ))
    }'
done

ops=(
    [\<]=lt [\<=]=le
    [\>]=gt [\>=]=ge
    [==]=eq [!=]=ne
    [+]=add [-]=sub
    [\*]=mul [/]=div
    [%]=mod [:]=match
)

match () {
    evaluate "$2"
    tmp2=$REPLY
    evaluate "$1"
    tmp1=$REPLY
    [[ $tmp1 =~ ^$tmp2$ ]]
    REPLY=${BASH_REMATCH[1]-${#BASH_REMATCH}}
}
index () {
    tmp=${1%%["$2"]*}
    REPLY=${#tmp}
}
length () {
    REPLY=${#1}
}
substr () {
    evaluate "$3"
    tmp3=$REPLY
    evaluate "$2"
    tmp2=$REPLY
    [[ $tmp2$tmp3 = *([0-9]) ]] || die non-integer argument
    REPLY=${1:$tmp2+1:$tmp3}
}

poparg () {
    REPLY=()
    for (( tmp = ${1-1}; tmp; tmp-- )) do
        REPLY+=("${args[-1]}")
        unset "args[-1]" || die syntax error
    done
}

evaluate () {
    if [[ $1 = length ]]; then
        poparg
        length "$REPLY"
    elif [[ $1 = @(match|index) ]]; then
        poparg 2
        "$1" "${REPLY[@]}"
    elif [[ ${args[i]} = substr ]]; then
        poparg 3
        "$1" "${REPLY[@]}"
    elif [[ ${ops[$1]} ]]; then
        poparg 2
        "${ops[$1]}" "${REPLY[@]}"
    else
        REPLY=$1
    fi
}

shunting_yard () {
    declare -A precedence=(
        [|]=1
        [&]=2
        [=]=3 [!=]=3
        [>]=3 [>=]=3
        [<]=3 [<=]=3
        [+]=4 [-]=4
        [\*]=5 [/]=5 [%]=5
        [:]=6
    )

    stack=()
    for token; do
        if [[ $token = *([0-9]) ]]; then
            args+=("$token")
        elif [[ $token = @(index|length|match|substr) ]]; then
            stack+=("$token")
        elif [[ ${precedence[$token]} ]]; then
            while [[ $stack ]] &&
                [[ ${stack[-1]} == @(index|length|match|substr) ||
                   ${precedence[${stack[-1]}]} -ge ${precedence[token]} ]] &&
                [[ ${stack[-1]} != '(' ]]; do
                args+=("${stack[-1]}")
                unset "stack[-1]"
            done
            stack+=("$token")
        elif [[ $token = '(' ]]; then
            stack+=("$token")
        elif [[ $token = ')' ]]; then
            while [[ $stack && ${stack[-1]} != '(' ]]; do
                args+=("${stack[-1]}")
                unset "stack[-1]"
            done
            if [[ $stack && ${stack[-1]} = '(' ]]; then
                unset "stack[-1]"
            else
                die syntax error
            fi
        else
            args+=("$token")
        fi
    done

    while [[ $stack ]]; do
        if [[ ${stack[-1]} = '(' ]]; then
            die syntax error
        fi
        args+=("${stack[-1]}")
        unset "stack[-1]"
    done
}

expr () {
    (( $# )) || die missing operands

    args=() i=0
    shunting_yard "$@"

    declare -p args
    op=${args[-1]}
    unset "args[-1]"
    evaluate "$op"
    echo "$REPLY"
}


expr "$@"



bash expr \( \( 15 / \( 7 − \( 1 + 1 \) \) \) \* 3 \) − \( 2 + \( 1 + 1 \) \)