Problem: Calc 2.0

Questions? Feel free to head to CS50 on Reddit, CS50 on StackExchange, the #cs50ap channel on CS50x Slack (after signing up), or the CS50 Facebook group.

Objectives

  • Interact with users at the command line

  • Defend against malicious users

  • Parse and process user input

  • Get better acquainted with functions and libraries

  • Use stacks

  • Pages 11 – 14 and 39 of http://www.howstuffworks.com/c.htm.

  • Chapters 6, 7, 10, 17, 19, 21, 22, 30, and 32 of Absolute Beginner’s Guide to C.

  • Chapters 7, 8, and 10 of Programming in C.

Academic Honesty

This course’s philosophy on academic honesty is best stated as "be reasonable." The course recognizes that interactions with classmates and others can facilitate mastery of the course’s material. However, there remains a line between enlisting the help of another and submitting the work of another. This policy characterizes both sides of that line.

The essence of all work that you submit to this course must be your own. Collaboration on problems is not permitted (unless explicitly stated otherwise) except to the extent that you may ask classmates and others for help so long as that help does not reduce to another doing your work for you. Generally speaking, when asking for help, you may show your code or writing to others, but you may not view theirs, so long as you and they respect this policy’s other constraints. Collaboration on quizzes and tests is not permitted at all. Collaboration on the final project is permitted to the extent prescribed by its specification.

Below are rules of thumb that (inexhaustively) characterize acts that the course considers reasonable and not reasonable. If in doubt as to whether some act is reasonable, do not commit it until you solicit and receive approval in writing from your instructor. If a violation of this policy is suspected and confirmed, your instructor reserves the right to impose local sanctions on top of any disciplinary outcome that may include an unsatisfactory or failing grade for work submitted or for the course itself.

Reasonable

  • Communicating with classmates about problems in English (or some other spoken language).

  • Discussing the course’s material with others in order to understand it better.

  • Helping a classmate identify a bug in his or her code, such as by viewing, compiling, or running his or her code, even on your own computer.

  • Incorporating snippets of code that you find online or elsewhere into your own code, provided that those snippets are not themselves solutions to assigned problems and that you cite the snippets' origins.

  • Reviewing past years' quizzes, tests, and solutions thereto.

  • Sending or showing code that you’ve written to someone, possibly a classmate, so that he or she might help you identify and fix a bug.

  • Sharing snippets of your own solutions to problems online so that others might help you identify and fix a bug or other issue.

  • Turning to the web or elsewhere for instruction beyond the course’s own, for references, and for solutions to technical difficulties, but not for outright solutions to problems or your own final project.

  • Whiteboarding solutions to problems with others using diagrams or pseudocode but not actual code.

  • Working with (and even paying) a tutor to help you with the course, provided the tutor does not do your work for you.

Not Reasonable

  • Accessing a solution to some problem prior to (re-)submitting your own.

  • Asking a classmate to see his or her solution to a problem before (re-)submitting your own.

  • Decompiling, deobfuscating, or disassembling the staff’s solutions to problems.

  • Failing to cite (as with comments) the origins of code, writing, or techniques that you discover outside of the course’s own lessons and integrate into your own work, even while respecting this policy’s other constraints.

  • Giving or showing to a classmate a solution to a problem when it is he or she, and not you, who is struggling to solve it.

  • Looking at another individual’s work during a quiz or test.

  • Paying or offering to pay an individual for work that you may submit as (part of) your own.

  • Providing or making available solutions to problems to individuals who might take this course in the future.

  • Searching for, soliciting, or viewing a quiz’s questions or answers prior to taking the quiz.

  • Searching for or soliciting outright solutions to problems online or elsewhere.

  • Splitting a problem’s workload with another individual and combining your work (unless explicitly authorized by the problem itself).

  • Submitting (after possibly modifying) the work of another individual beyond allowed snippets.

  • Submitting the same or similar work to this course that you have submitted or will submit to another.

  • Using resources during a quiz beyond those explicitly allowed in the quiz’s instructions.

  • Viewing another’s solution to a problem and basing your own solution on it.

Assessment

Your work on this problem set will be evaluated along four axes primarily.

Scope

To what extent does your code implement the features required by our specification?

Correctness

To what extent is your code consistent with our specifications and free of bugs?

Design

To what extent is your code written well (i.e., clearly, efficiently, elegantly, and/or logically)?

Style

To what extent is your code readable (i.e., commented and indented with variables aptly named)?

To obtain a passing grade in this course, all students must ordinarily submit all assigned problems unless granted an exception in writing by the instructor.

Adding any Updates

Start off by opening up CS50 IDE and then type

update50

within a terminal window to make sure your workspace is up-to-date. If you somehow closed your terminal window (and can’t find it!), make sure that Console is checked under the View menu, then click the green, circled plus (+) in CS50 IDE’s bottom half, then select New Terminal. If you need a hand, do just ask via the channels noted at the top of this specification.

Next, navigate to your workspace directory and create a new subdirectory inside of it called chapterA (Remember how?) Then navigate inside that directory. (Remember how?)

Finally, take a few minutes to watch Doug’s video on stacks.

Divide and Conquer, again

In this problem, you will be tasked with implementing a not so simple command-line based calculator program. (Hmm…​ that sounds familiar.) Your program will accept inputs like this (wherein underlined text represents user input):

username@ide50:~/workspace/chapterA/ $ ./calc2 + - 3 4 5
4.000000

or, indeed like this (allowing the user to perform some basic floating-point arithmetic)

username@ide50:~/workspace/chapterA/ $ ./calc2 x - 3.4 5.6 7.9
-17.3799999

such that the user can perform all five of the basic math operations that C permits — addition, subtraction, multiplication, division, and modulo.

But wait. Part of that isn’t familiar.

x - 3.4 5.6 7.9

What’s that?

That, actually, is what is known as prefix notation. Though not as common as the infix notation we all learned about in elementary school, it turns out that prefix notation and its closely related cousin postfix notation (also known, respectively, as Polish and Reverse Polish notation) are much easier for machines to parse.

Converting the above to more familiar infix notation would result in the expression (3.4 - 5.6) x 7.9. For more on prefix notation, check out its Wikipedia page and/or Google!

Obviously, you’re going to need to do math at some point, but you may have already done that. Can you leverage some of your code from your first version of Calc?

Stacks on Stacks on Stacks

So, how should we go about implementing this prefix calculator? One easy approach might be to use a stack. Let’s see why.

The basic idea behind prefix notation is that an operation operates on the two numbers immediately to its right, and all three (the operator and its so-called operands) are then replaced in the line by the answers, moving from right to left[1].

Here’s an example using one fairly straightforward approach:

+ - / 4 2 24 x 8 9

The first operation we encounter going right to left is x (multiplication). So we look to the two operands to its right (8 9), multiply them together, and leave the result where x 8 9 used to be:

+ - / 4 2 24 72

The next operator from right to left is /. 4 divided by 2 is of course 2, and so we leave 2 where / 4 2 used to be:

+ - 2 24 72

Next up is - 2 24, replaced by -22 (the result of 2 - 24):

+ -22 72

And all that then remains is -22 + 72, or 50!

Visually, this approach of "finding the rightmost operator and applying it to the two numbers to its right" is an intuitive way for humans to parse prefix notation, but computers can be a bit smarter about this, without ever having to look at each operand or operator more than once, if instead we store all the information in a stack as we see it.

If the computer parsed this input by starting at the right side (aka the last element of argv) and pushing numbers onto a stack as it came across them, then when it came upon an operation all that would need to happen is to pop the top two numbers off the stack, apply the operation, and push the result back on!

Calculating, Calculating

Like Calc, you will be expected to take all input in the command line. And like Calc, floating point numbers and integers are both fair game. Unlike Calc, you may not assume well formatted input. Here is what you can assume:

  • There will never be more than 20 numbers in the stack

That’s it.

Note that you cannot assume that everything will be a float or an operation, or that the order of numbers and operands will work out nicely. Better check those yourself!

Inside of calc2.c (where you should write your calculator), use the following definition of stack:

typedef struct
{
   int size;
   float nums[MAXNUMS];
}
stack;

And #define MAXNUMS 20 somewhere above.

That’s all you’ll have for this one though. No distro, just this specification and a definition of a stack datatype to include in your file!

To test the correctness of your prefix calculator, you can run check50 with:

check50 1617.chapterA.calc2 calc2.c

And of course feel free to play with the staff solution to perform extra tests beyond those articulated in check50:

~cs50/chapterA/calc2

This was Calc 2.0.


1. Not necessarily right to left, but in this example it might be easiest to follow doing it that way.