Beginner Programming Challenge #11

[falconindy]

Submitting a partial rewrite that uses only stack allocated memory and has some mild improvements/fixes. I don't really consider myself a beginner in programming, but I'm still pretty green when it comes to C. Same Makefile as from my last entry can be used here.

#include <ctype.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define CONTINUE 1
#define BREAK 0

#define STACK_SIZE 64

/* operand stack */
static double opstack[STACK_SIZE];
static double *stackptr;

/* default runtime options */
static int verbose = 0;
static int precision = 3;

/* protos */
static char *strtrim(char*);
static int parse_expression(char*);
static int parse_operand(char*, double*);
static int parse_operator(char);
static void resetstack();

char *strtrim(char *str) {
  char *pch = str;

  if (str == NULL || *str == '\0')
    return str;

  while (isspace(*pch)) pch++;

  if (pch != str)
    memmove(str, pch, (strlen(pch) + 1));

  if (*str == '\0')
    return str;

  pch = (str + strlen(str) - 1);

  while (isspace(*pch))
    pch--;

  *++pch = '\0';

  return str;
}

void resetstack() {
  if (stackptr == &opstack[0])
    return;

  if (verbose) { /* Dump individual items on the stack */
    printf(":: Stack Dump :: ");
    while (stackptr != &opstack[0])
      printf("%.*f ", precision, *--stackptr);
    putchar('\n');
  } else /* Just reset the pointer */
    stackptr = &opstack[0];

}

/** parse operations */
int parse_operand(char *token, double *operand) {
  char *endPtr;

  *operand = strtod(token, &endPtr);
  if (*operand == HUGE_VAL) {
    fprintf(stderr, "!! Input overflow.\n");
    return 1;
  }
  if (token + strlen(token) != endPtr) {
    fprintf(stderr, "!! Bad input: %s\n", token);
    return 1;
  }

  return 0;
}

int parse_operator(char operator) {
  double op1, op2;

  op2 = *--stackptr;
  op1 = *--stackptr;

  if (verbose)
    printf(":: %.*f ", precision, op1);

  switch (operator) {
    case '+': op1 += op2; break;
    case '-': op1 -= op2; break;
    case '*': op1 *= op2; break;
    case '^': op1 = pow(op1, op2); break;
    case '/': if (op2 == 0) {
                fprintf(stderr, "!! Divide by zero\n");
                return 1;
              }
              op1 /= op2; 
              break;
    case '%': if (op2 == 0) {
                fprintf(stderr, "!! Divide by zero\n");
                return 1;
              }
              op1 = (int)op1 % (int)op2;
              break;
  }

  if (verbose)
    printf("%c %.*f = %.*f\n", operator, precision, op2, precision, op1);

  if (op1 == HUGE_VAL) {
    fprintf(stderr, "!! Result overflow\n");
    return 1;
  }

  *stackptr++ = op1;

  return 0;
}

int parse_precision(char *p) {
  char *endPtr;
  int pre;

  pre = (int)strtol(p, &endPtr, 10);
  if (endPtr != p + strlen(p)) {
    fprintf(stderr, "!! Bad precision specified\n");
    return 1;
  } else {
    precision = pre;

    if (precision < 0) /* clamp negative numbers to 0 */
      precision ^= precision;
    printf(":: Precision set to %d decimal places.\n", precision);
  }

  return 0;

}

int parse_expression(char *expr) {
  if (strlen(strtrim(expr)) == 0) /* empty string passed, we're done */
    return BREAK;

  char *token;
  static const char *operators = "+/*-%^";
  double operand;

  while ((token = strsep(&expr, " \n"))) {
    if (strlen(token) == 0) continue;

    if (*token == ':') /* precision specified */
      parse_precision(++token);
    else if (strchr(operators, *token) && strlen(token) == 1) { /* operator */
      if (stackptr - opstack < 2) {
        fprintf(stderr, "!! Malformed expression -- too few operands.\n");
        return CONTINUE;
      }

      if (parse_operator(*token) > 0) {
        return CONTINUE;
      }
    } else { /* it's an operand, or it's bad input */
      if (parse_operand(token, &operand) > 0) /* parsing failed on bad input */
        return CONTINUE;

      if (stackptr == &opstack[STACK_SIZE]) { /* stack overflow */
        fprintf(stderr, "!! Stack overflow. Expression too large.\n");
        return CONTINUE;
      }

      *stackptr++ = operand;
    }
  }

  if (stackptr - opstack > 1)
    fprintf(stderr, "!! Malformed expression -- too many operands.\n");
  else if (stackptr - opstack == 1) {
    printf(" = %.*f\n", precision, *--stackptr);
  }

  return CONTINUE;
}

int main(int argc, char *argv[]) {
  char buf[BUFSIZ + 1];

  if (argc > 1 && strcmp(argv[1], "-v") == 0) {
    fprintf(stderr, "::Stack dumps enabled::\n");
    verbose = 1;
  }

  stackptr = &opstack[0]; /* initialize stack */

  do {
    resetstack();
    printf("> ");
    buf[0] = '\0';
    fgets(buf, BUFSIZ, stdin);
  } while (parse_expression(buf));

  return 0;
}

[schauerlich]

Alright, the time has come to announce the winner. Drum roll please...

Our winner is...
falconindy!

His entry may have come in late, but it's a well-done, functional entry, written in C to boot! A refreshing change from what seems to be a python-dominated challenge. Not that that's a bad thing, per se, but variety is the spice of life.

Congratulations! It's your turn to host the challenge. Once you've got an idea, make a thread and let the fun begin all over again!

[patrickaupperle]

Congratulations falconindy! When can we expect the next challenge?

[texaswriter]

Congratulations FalconIndy. I did like how concise and short yours was.

[falconindy]

Fun fun. I'll poke around and see if I can't find something fitting by the end of the day.

edit: it's up! Enjoy!

[Junkieman]

Well done falconindy!

[thepopasmurf]

Here's a late entry. I am not a beginner programmer in general but I am only just learning Ocaml (and functional languages in general).

(* Reverse Polish Notation *)
exception Stack_error of string;;

(* Required for % operation because built in % works for ints *)
let floatMod a b =
	let ai = int_of_float a in
	let bi = int_of_float b in
	float_of_int (ai mod bi);;

let rec execute commList stack =
	match commList with
	| [] -> (
		match stack with
		| x::[] -> x
		| _ -> raise (Stack_error "Invalid answer" );
			)
	| "+"::rest -> begin
		match stack with
	    | x::y::xys -> execute rest ((x+.y)::xys);
		| _ -> raise (Stack_error "Not enough arguments");
			end
	| "-"::rest -> begin
		match stack with
		|x::y::xys -> execute rest ((y-.x)::xys);
		| _ -> raise (Stack_error "Not enough arguments");
			end
	| "*"::rest -> begin
		match stack with 
		|x::y::xys ->	execute rest ((x*.y)::xys);
		| _ -> raise (Stack_error "Not enough arguments");
			end
	| "/"::rest -> begin
		match stack with
		|x::y::xys -> execute rest ((y/.x)::xys);
		|_ -> raise (Stack_error "Not enough arguments");
			end
	| "%"::rest -> begin
		match stack with
		|x::y::xys -> execute rest ((floatMod y x)::xys);
		|_ -> raise (Stack_error "Not enough arguments");
		end
	| "^"::rest -> begin
		match stack with
		|x::y::xys -> execute rest ((y**x)::xys);
		|_ -> raise (Stack_error "Not enough arguments");
		end
		
	| str::rest -> let re = Str.regexp "[0-9]+\\.?[0-9]*$" in
		if Str.string_match re str 0 then 
			execute rest ((float_of_string str)::stack)
	        else (raise (Stack_error "Invalid input"));;
		
(* Runs the program in the terminal *)
let rec go value = 
	if value then begin
	try
		print_string " -> ";
		let input = read_line() in
		if input="q" then go false else
		let commandList = Str.split (Str.regexp " ") input in
		print_float (execute commandList []);
		print_string "\n";
		go true;
	with Stack_error s -> print_endline s; go true;
	end
	else ();;
		
print_endline "Type 'q' (lowercase) to quit the program";
go true;;

This program uses regular expressions. If anyone wants compile this program they need to include the str.cma / str.cmxa modules.

ocamlc -o output str.cma file.ml

ocamlopt -o output str.cmxa file.ml

[schauerlich]

Well, when I made this challenge, I did it in python... but as I'm learning ruby I decided to reimplement it in that. Enjoy.

class Calculator
    def eval(exp)
        tokens = exp.gsub('^', '**').split.map do |token|
            begin
                Float(token)
            rescue ArgumentError
                if %w{+ - / * % **}.include? token
                    token
                else
                    raise ArgumentError.new "Unrecognized token"
                end
            end
        end
        
        stack = []

        tokens.each do |token|
            if token.class == Float
                stack.push( token )
            else
                right, left = stack.pop, stack.pop

                if right == nil or left == nil
                    raise ArgumentError.new "Not enough operands"
                end

                begin
                    stack.push( left.send(token, right) )
                rescue ZeroDivisionError
                    raise ArgumentError.new "Division by zero"
                end
            end
        end
        if stack.length == 1
            stack.pop
        else
            raise ArgumentError.new "Too many operands"
        end
    end
end


if __FILE__ == $0
    calc = Calculator.new

    while true
        print "> " 
        input = gets.strip.downcase

        Process.exit! if input == 'q'
        next if input.empty?

        begin
            puts calc.eval( input )
        rescue ArgumentError => err
            puts err
        end
    end
end

[Coalwater]

> 45 6 + / & 4
Unrecognized token

In my code this case generated not enough operands, because it tries to do the division before noticing the "&" , is this considered correct ? or do i need to scan the whole string first?

[schauerlich]

In my code this case generated not enough operands, because it tries to do the division before noticing the "&" , is this considered correct ? or do i need to scan the whole string first?

As long as it doesn't segfault or have an uncaught exception, it's fine. What happens on the input "5 10 &" ?