digit(X) :-  member(X, "0123456789").

num(Num, [Digit|L], Res, M) :-
    digit(Digit), !,
    num(Num*10+Digit-48, L, Res, M).
num(Num, L, Res, L) :- Res is Num.

tokenize(0'+,+). tokenize(0'-,-). tokenize(0'*,*). tokenize(0'/,/).
tokenize(0'(,'('). tokenize(0'),')').

tokenize([],[]).
tokenize([Ascii|L], [Symbol|M]) :-
    tokenize(Ascii, Symbol),
    tokenize(L, M).
tokenize([Digit|L], [Num|M]) :-
    digit(Digit),
    num(Digit-48, L, Num, R),
    tokenize(R, M).

%main :- tokenize("(1-2)*345+0",X), write(X),nl,fail.

% symbol kind
operator(+). operator(-). operator(*). operator(/).
bra('('). ket(')').

% cakculate a simple opeation
calc(X,+,Y,Z) :- Z is X+Y.
calc(X,-,Y,Z) :- Z is X-Y.
calc(X,*,Y,Z) :- Z is X*Y.
calc(_,/,0,_) :- !, fail. % can’t divide by 0
calc(X,/,Y,Z) :- 0 is mod(X,Y), Z is div(X,Y). % exact division

% operator precedence
precedence(+,1). precedence(-,1). precedence(*,2). precedence(/,2).

% Shunting-yard algorithm
eval_op(X, L, [A,B|Nums], [Y|Ops], Res) :-
    precedence(X, Px),
    precedence(Y, Py),
    Px =< Py, !,
    calc(B, Y, A, C),
    eval(L, [C|Nums], [X|Ops], Res).
eval_op(X, L, Nums, Ops, Res) :-
    eval(L, Nums, [X|Ops], Res).

eval_ket(L, Nums, [X|Ops], Res) :-
    bra(X), !,
    eval(L, Nums, Ops, Res).
eval_ket(L, [X,Y|Nums], [Op|Ops], Res) :-
    calc(Y, Op, X, Z),
    eval_ket(L, [Z|Nums], Ops, Res).

eval([Tk|L], Nums, Ops, Res) :-
    (   number(Tk) ->
        eval(L, [Tk|Nums], Ops, Res)
    ;   operator(Tk) ->
        eval_op(Tk, L, Nums, Ops, Res)
    ;   bra(Tk) ->
        eval(L, Nums, [Tk|Ops], Res)
    ;   ket(Tk) ->
        eval_ket(L, Nums, Ops, Res)
    ).
eval([], [X,Y|Nums], [Op|Ops], Res) :-
    calc(Y, Op, X, Z),
    eval([], [Z|Nums], Ops, Res).
eval([],[N],[],N).

% eval(-String, +Value)
eval(Str, Val) :-
    tokenize(Str, TokenList),
    eval(TokenList, [], [], Val).

% print a string
puts([X|L]) :- put_code(X),puts(L).
puts([]).

%main :- member(L,["1+2*3","(1+2)","1","1+2","1+2-3","(1+2)*3","1+(2*3)"]),puts(L),nl,eval(L,R),write(=),write(R),nl,fail.

% possible next character
after(X, Y) :-
    (   member(X, "0123456789") ->
        member(Y, "0123456789+-*/)")
    ;   member(X, "+-*/(") ->
        member(Y, "123456789(")
    ;   member(X, ")") ->
        member(Y, "+-*/)")
    ).

choose([Constr], Prev, Avoid, [Ascii]) :-
    member(Ascii, Constr),
    member(Ascii, "0123456789)"),
    \+(member(Ascii,Avoid)),
    after(Prev, Ascii).
choose([Constr|L], Prev, Avoid, [Ascii|M]) :-
    member(Ascii, Constr),
    after(Prev, Ascii),
    \+(member(Ascii,Avoid)),
    choose(L, Ascii, [Ascii|Avoid], M).

xchoose([Constr], Prev, Avoid, [Ascii]) :-
    member(Ascii, Constr),
    member(Ascii, "0123456789)"),
    member(Ascii,Avoid),
    after(Prev, Ascii).
xchoose([Constr|L], Prev, Avoid, [Ascii|M]) :-
    member(Ascii, Constr),
    after(Prev, Ascii),
    member(Ascii, Avoid),
    choose(L, Ascii, Avoid, M).

choose(Constrs, String) :-
    choose(Constrs, 40, [], String).

find(Constrs, Target, String) :- choose(Constrs, String), eval(String,Target).

%main :- T="0123456789+-*/()", find([T,T,T,T],12,Str), puts(Str), nl, fail.


main :- find([
"0124689+-*/()",
"012689+-*/()",
"0124689+-/()",
"0124689+-*/()",
"0124689+-*()",
"0124689+-*/()",
"+",
"012489+-*/()"
],132,Str), puts(Str), nl, fail.