creating stack in sml

Question

I am trying to create stack in sml, I have tried using list; but I am having trouble to add elements into the list. I'm trying to read lines from the input file, say that if the line says:

push 5
push 9
add
quit

Then I want the output file to be:

14

since 5+9 is 14. So far, I was able to create boolean functions that recognizes if the line is push or has numeric.

fun is_digit (c) = #"0" <= c andalso c <= #"9";
fun is_Push (c) = String.isSubstring "push" c;

fun stack(inFile : string, outFile : string) =
let
        val ins = TextIO.openIn inFile;
        val outs = TextIO.openOut outFile;
        val readLine = TextIO.inputLine ins;
        val it = []: string list;
        fun helper(readLine : string option) =
            case readLine of
                NONE => ( TextIO.closeIn ins; TextIO.closeOut outs)
                | SOME(c) => (
                    if is_Push c 
                    then
                    let
                        val number = String.sub(c,5);
                        val numbChar = Char.toString number;

                    in
                        val myList = nil :: numbChar;
                        TextIO.output(outs, Int.toString(length myList))
                    end

                    else 
                        TextIO.output(outs, "aaa\n");
                        helper(TextIO.inputLine ins))

in
        helper(readLine)
end

Answer 1

I would split the problem into separate concerns; in particular, separate the functions that perform I/O from pure functions. This makes them more testable and easier to compose later on.

1. Define an abstract representation of stack commands and convert your file into this abstract representation. Define an exception type for handling incorrect stack commands. This means that your data representation is sanitized.

   datatype StackCommand = Push of int
                         | Pop
                         | Add
                         | Quit
   
   exception InvalidCommand of string * string list
   

2. Create reusable helper functions for reading lines from files.

   fun isLinebreak c = c = #"\n"
   
   fun inputLines filename =
       let val fd = TextIO.openIn filename
           val content = TextIO.inputAll fd
           val _ = TextIO.closeIn fd
       in String.tokens isLinebreak content
       end
   

3. Separate the concern of parsing a single command into one function, and make it so that it requires the right number of arguments for the right command.

   fun parseCommand line =
       case String.tokens Char.isSpace line of
            ["push", s] => (case Int.fromString s of
                                SOME i => Push i
                              | NONE => raise InvalidCommand (push, s))
          | ["pop"] => Pop
          | ["add"] => Add
          | ["quit"] => Quit
          | (cmd::args) => raise InvalidCommand (cmd, args)
   
   val parseCommands = map parseCommand
   
   val inputCommands = parseCommands o inputLines
   

4. Define your stack as a list of integers. Given a stack, evaluate a list of commands by iterating this list and update stack according to the command.

   type stack = int list
   exception StackError of stack * StackCommand
   
   fun evalCommand stack (Push i) = i::stack
     | evalCommand (_::stack) Pop = stack
     | evalCommand (i::j::stack) Add = i+j::stack
     | evalCommand stack Quit = stack
     | evalCommand stack cmd = raise StackError (stack, cmd)
   
   fun evalCommands stack [] = stack
     | evalCommands stack (Quit::_) = stack
     | evalCommands stack (cmd::cmds) =
       evalCommands (evalCommand stack cmd) cmds
   

You can then use either evalCommands on the return value of inputCommands, or you can use evalCommand in a REPL that reads interactively from standard input.

Answer 2

I would recommend pushing and popping to take place at the front of the list, with the actual pushing and popping implemented by pattern matching, with the (modified) stack passed around as an argument.

Say you have a list of strings which look like e.g.

["push 5", "push 9", "add", "quit"]

and you want to process this string according to the following rules:

1) If the string is of the form "push d" (where d is a single digit) then
   push the integer value of d onto the stack

2) If the string is of the form "add" then pop the first two elements off
   the stack, add them, and push the sum back on

3) If the string is "quit" then return the top of the stack

In case 3, you actually return a value, in the other cases -- call the processing function on the tail of the list of lines and with an appropriately modified stack. Something like:

fun process ([], stack) = 0
|   process ("quit"::lines, i::stack) = i
|   process ("add"::lines, i::j::stack) = process(lines,(i+j)::stack)
|   process (s::lines, stack) = 
        let 
            val d = String.sub(s,5)
            val i = Char.ord d - Char.ord(#"0")
        in
            process(lines,i::stack)
        end;

I threw in a basis case of returning 0 on an empty list of lines, but provided no real error checking. In particular -- it will crash with a run time error if "add" is encountered when the stack has fewer than 2 elements, and "quit" will cause a crash if called with an empty stack.

To use this, call it with the list of lines and an empty stack:

- process (["push 5", "push 9", "add", "quit"],[]);
val it = 14 : int

Answer 3

Use @ to add to a list. E.g. it = it @ [number];

By the way, I'd suggest you rename c as s or line because c is normally used for single characters, not strings of characters. It's confusing to a human reader of your program.