Introduction:

In this lab you will be writing another calculator, but this one can take in long expressions in  reverse  Polish notation (also  known as postfix notation). You’ll be implementing another two libraries.  One library will implement a data structure known as a stack.   The other library will utilize your stack to parse Reverse Polish Notation strings.  Finally, you will write a main file that uses your string-parsing library to make an

interactive calculator.

Reading:

.    K&R – Sections 5.1-5.3, 6.1-6.2

Concepts:

.    String manipulation

.    Structs

.    Stacks

.    Error Handling

Required Files:

.    stack.c

.    stack_test.c

.    rpn.c

.    rpn_test.c

.    Lab04_main.c

.    README.md

o stack.h — Contains the  spec  and  prototypes for  the functions that you will implement in Stack.c along with brief descriptions of each function. Add this file to your project directly.

o rpn.h – Contains the spec and prototypes for functions to parse Reverse  Polish  Notation  strings.   Also  includes  a  list  of  errors that the RPN parser can return.

o  BOARD .c/.h — contains  initialization  code for the  UNO32  along with standard #defines and system libraries used . Also includes the standard fixed-width datatypes and error return values.

o  GNUmakefile — used for compiling this lab on Linux .

. Edit these files:

o stack_test.c,  rpn_test.c – starter  code for your test  harnesses. Build them  up to  produce thorough test  harnesses.   (they are included  as  stack_test_template.c  and  rpn_test_template.c,  so rename them).

o Lab04_main.c – starter code for your main calculator.     Expand on   the   code   here   to   make   a   calculator   that   meets   the

assignment requirements.

. Create these files:

o  rpn .c,  stack .c – Create  these  files  to  implement  the  functions specified in their respective .h files.

Grading:

There are 19 points that can be awarded in this assignment.  It is scored out of 18, so there is 1 point of“cushion. ”

. 9 points: Automated components:

o 4   points – Correctly   implementing  all  functions  declared   in Stack .h

0.5 per function that works when called correctly

1.0 – all functions return errors as appropriate

o  5 points – Correctly implementing all functions in rpn .c

4 point: Parser behavior

. 1 – handles minimal RPN expressions

. 1 – handles complex RPN expressions

. 1 – handles all 6 rpn errors correctly

. 1 – Passes all tests (tough!)

1 point: ProcessBackspaces works correctly

. 10 points: Human components:

o  2 points (1 for each test harness):

does thorough tests of each function and gives readable

output

o 3 points:  Calculator functionality

2 – User interface (greets, prompts, prints, loops)

2 – Handles all 5 error messages correctly and gracefully

o  3 points:   Code style

2 points:   Readability and style guidelines

1 point:   Program structure

o  2 points: README

1 point:   Contains a full lab report

1 point:  Clear communication and insightful ideas

. Deductions:

o NO CREDIT for sections where required files don't compile

o  -2 points: at least one  compilation warning

o  - 1 printing in any functions other than main()

o  - 1 using magic numbers

o At grader discretion, other deductions  may  be  made for things not  covered  in this  rubric,  such  as  bad  programming  practice, extremely unreadable code, etc.

o  It  must  compile  within  MPLABX.  Code  that  does  not  compile within MPLABX will receive no credit.

Assignment requirements:

general:

o  No magic numbers in this lab (not even for Booleans)!

Use  the  constants  that  are  #defined  or   enum{}’d  in BOARD.h, stack.h, and rpn.h where appropriate

#define  or  declare your  own  constants for your  main() files.

. One  exception:    You  may  use  magic  numbers  for

expected return values in your test harnesses .

o No stack functions should printf(), scanf(), or use any other UART activity.

stack_test.c:

o Test each function thoroughly.

Be sure to test correct-use cases and all error cases.

Make at least two   meaningfully   different   tests   per function.

o Print a clear, readable, concise record of which tests passed and which failed

rpn.c:

o Implement    both   of   the   functions   whose    prototypes   and specifications are in the header file stack.h.

RPN_Evaluate must parse the user input into a sequence of  string  tokens.  We  recommend  using  strtok() from string.h to perform tokenization, though other approaches are possible. Consulting the strtok() man page will prove helpful.

RPN_Evaluate should not print to or read from the UART.

RPN_Evaluate should use the functions in stack.h

o Note that ProcessBackspaces is only worth 1 point, so you may want to save it until the end.

rpn_test.c:

o Test each function thoroughly.

RPN_Evaluate() will require many tests to test thoroughly. Tests  should  grow  in  complexity,  with  each  test  string testing something new.

Return  NO_ERROR when the string  is successfully  parsed. If called with an invalid RPN string, return the appropriate error as enum{}’d in rpn.h.

o Print a clear, readable, concise record of which tests passed and which failed

Lab04_main.c:

o Greet the user once on startup

o  Prompt the user for an RPN string that includes doubles and the

4 arithmetic operators: + - / *

Your input string should be able to handle up to 60 chars, not including a trailing newline or null.

Make sure that your calculator handles doubles properly

and  that  all  calculations  are  done  with  values  of  type

“double”. This includes 0.0 and negative numbers.

. You   may   use   scanf(),   fgets(),   or   fgetc(),

according to your preference .

o Return to prompting the user for another RPN string to calculate.

o If an  error  is encountered,  print an appropriate  error  message and handle it gracefully.

There  are  5  possible  errors:     rpn.h  defines  6  errors. Additionally, handle the error when the user enters more than 60 characters.

Error messages should be more human-readable than the enum{}’d constants,  helping a  naive  user to  understand the issue.

README.md:

o This  will  follow  the  same  rough  outline  as  a  lab  report  for  a regular  science  class.     It  should  be  on  the  order  of  three paragraphs with several sentences in each paragraph.

First you should list your name & the names of colleagues who you have collaborated with.1

In the next section you should provide a summary of the lab in your own words.  Highlight what you thought were the important aspects of the lab. If these differ from how the lab manual presents things, make a note of that.

The  following  section  should  describe  your  approach  to the lab. What was your general approach to the lab? Did you read the manual first or what were your first steps? What went wrong as you worked through it? What worked well?  How would you approach this lab differently  if you were to do it again? How did you work with other students in the class and what did you find helpful/unhelpful?

The  final  section  should  describe  the   results  of  you implementing  the  lab.  How  did  it  end  up  finally?  How many hours did you end up spending on it? What did you like about it? What did you dislike? Was this a worthwhile lab? Do you have any suggestions for altering it to make it better? What were the hardest parts of it? Did the points distribution for the grading seem appropriate? Did the lab manual cover the  material  in enough detail to start you off?  Did  examples  or  discussions  during  class  help  you understand   this   lab   or   would   more  teaching   on  the concepts in this lab help?

Doing this Lab on Linux:

This lab has multiple parts and instead of calling gcc multiple times we are instead going to start using the make system instead. We will go over how it

works in class but the commands needed are below.   For these to work the

file‘GNUmakefile’needs to be in the same directory as the rest of your files, it is only used when compiling on Linux.

.    $ make

o This command will create the final executable named Lab4

.    $ make stack_test

o This command will compile your stack test and stack library files into the executable stack_test

.    $ make rpn_test

o This  command  will  do  the  same  thing  but  for  your  rpn  test making an executable named rpn_test

Additionally, as is common in embedded software, there is no quit command for this lab; you will need to use‘ctrl-c’on Linux to exit your final calculator.

Program Flow

This  program  follows  a  very  similar  outline to  the  calculator  you  did

previously, but takes a few more steps to get to the user input because you will be parsing a string. Here’s an overview in pseudo-code:

For  this  program  you  will  need  to  be  more  careful  about  handling unexpected  input.  For  example  the  user  may  not  enter  a  properly formatted  RPN  string.  Or  the  final  calculation  could  result  in  two elements in the stack.  Each“ ---”above is a place where it would be

useful to check for an error.

String Handling:

In this lab, you will have to work with strings using a level of detail that we have not yet explored in this class.  In particular, you will have to    perform a few operations that may be new to you.

Tokenization

The central string operation in this lab is called tokenization .  This    means taking a long string that is separated by space characters (or

some other delimiter) and breaking it into substrings.  For example, the string:

“Hello World, + !5403”

Is a string with 4 tokens (using a ASCII 32 / hex 0x20 /‘‘ (space) character as a delimiter)

.    +

.     !5403

There are various ways to do this, but the string .h function strtok() is

probably the best.

strtok() is called in 2 ways.

.     Initialization:  To use strtok() on a new string, pass it a pointer to the string, along with a delimiter .     It will  modify the string  in place,  replacing  each  delimiter  with  a  null  character .     It  also returns a  pointer to the first token, which you already  knew (it’s

the same pointer that you passed in!)

.      Subsequent   tokens:   To   get   the   next   token   from   a   previous

string, pass it a null pointer.   strtok() will return a pointer to the next token.  If it already returned the last token in the string, it will return null, signifying that the string has been consumed.

Other useful functions

Here  are  some  other  useful  string .h  functions.     Documentation  is

available   under   Help->Topics->MPLAB   XC32   Toolchain   ->   XC32

Standard  Libraries->Standard  C  Libraries.  These  functions  are  also

described  online  (see  Wikipedia's  string.h  entry),  in  K  &  R,  and  in Section 3 of the system man pages (as in,‘man 3 strlen’) .

strlen() –  Returns the number of characters in a string (the number of characters in a character array before the first null character).