联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codinghelp

您当前位置:首页 >> C/C++编程C/C++编程

日期:2021-04-04 02:33

Overview

For this project you'll build out a stack-based calculator that uses RPN notation.

Organization

You should end up with at least eight source files in your project, plus one file of captured

output.

main.c driver file for the problem set

node.h

node.c declaration and implementation of a single node

stack.h

stack.c declaration and implementation of stack operations

rpn.h

rpn.c declaration and implementation of the RPN evaluator

errors.h definitions of strings for error codes

ps4results.txt

Your code in main.c should be doing very little work on its own -- it basically will just be making

calls into the evaluate( ) function in rpn.c:

result = evaluate(expression, &status);

Note that node.h and node.c will be very similar to the node that you used in PS3, but it needs

to carry information about its contents:

typedef struct node {

double value;

int type;

node *next;

} node;

Use an enumeration to define type as either OPERATOR or NUMBER, and adjust createNode( )

from PS3 as necessary to accommodate the new fields.

Stack operations

Stacks have three primary operations, and you'll need to implement all three:

push(node) Push a node onto the stack

node* pop( ) Pop the top of the stack

node* peek( ) Return a reference to the node on top of the stack

In addition, implement a clearStack( ) function that resets the stack to empty, freeing any

nodes that were there previously. This should be called prior to each evaluation.

Stacks work from the top, so a push( ) will result in HEAD pointing to the pushed node, and the

pushed node pointing to the former HEAD. Similarly, a pop( ) will return the top node on the

stack and set HEAD to point to the former second node.

You are of course welcome to write additional helper functions. For example, it might be useful

to write a bool stackEmpty( ) function, or a function to return the type of a node, or maybe

one to print the stack that you could use for debugging.

Because these functions are working with node pointers, they will need to handle errors related

to the pointers (for example, null pointers and the return status from malloc( ) ).

Building the stack

Write a function in rpn.c called evaluate( ) that takes two parameters: the expression to

evaluate, and a reference to a status variable.

double evaluate (char* expression, int* status)

In evaluate( ), use the function strtok( ) (from <string.h>) to parse the input string.

The input string will comprise numbers and operators separated by a single space. For

example:

char expression[ ] = {"40 2 +"};

Keep in mind that strtok( ) involves two different calls, one to 'prime' the algorithm, and a

second in a loop to parse the remainder of the tokens. Each call to strtok( ) will result in a new

node being malloc'd and pushed. Once the calls to strtok( ) are complete, the stack will be built

and you can start evaluating the expression.

The string function strstr( ) is a good one to use to determine whether a token is a number

or an operator. You'll also need to convert the string returned from strtok into a number.

Evaluating expressions

Your calculator should evaluate the following five mathematical operators:

+ - / * ^ (exponentiation using recursion)

Use a switch statement to perform these calculations.

The problems:

PS4.0: Evaluate expressions

Once you've done all the setup work writing node, stack, and evaluate functions, evaluate

these expressions, capturing the result in ps4results.txt. If an error occurred, capture the error

message in the ps4results.txt file.

1. "24.2 12 / 3 / 17 + +"

2. "+"

3. "17 22 / 4 * 16 -"

4. "2 8 ^ 3 /"

5. "17 22 33 / 4 + 2"

6. ""

7. "8 7 + 6 - 5 / 4 * 3 ^"

Calculations using a stack and RPN

Reverse Polish Notation is a way of writing and evaluating mathematical expressions that is

commonly used in industries such as engineering and finance. One of its biggest advantages is

that there are no parentheses to alter precedence, and so calculation flows from left to right

without jumping around. It is often the case that software offering infix notation (where the

operator is between the operands) will first convert the infix expression to postfix (where

operators follow their operands, as in RPN) prior to performing a calculation.

For example, to write the expression 24 + 18 in RPN: 24 18 +.

RPN typically uses a stack to evaluate expressions. Each value in the expression (either a

number or an operator) is called a token. The algorithm looks like this:

1. Start with an empty stack

2. Read a token and create a node from it, marking it as either NUMBER or OPERATOR; use

malloc( ) to allocate space for the node

3. If the node contains a number, push it onto the stack

4. If the node contains an operator

A. Pop two values

B. Apply the operator

C. Push the result (in a new node) to the stack

When you've reached the end of the expression, there should be just one node on the stack,

holding the evaluation of the expression.

Note that we are only working with operators that take two values for this assignment.

Don't forget to call free( ) on any node that is being discarded.


版权所有:留学生编程辅导网 2020 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp