165 lines
8.2 KiB
HTML
165 lines
8.2 KiB
HTML
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
|
||
|
|
<!-- saved from url=(0063)http://students.cs.byu.edu/~cs235headta/homework/labs.php?lab=4 -->
|
||
|
|
<html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
|
||
|
|
|
||
|
|
<title>CS 235 - Labs</title>
|
||
|
|
<link rel="stylesheet" type="text/css" href="./lab04_files/main.css">
|
||
|
|
<link rel="stylesheet" type="text/css" href="./lab04_files/labs.css">
|
||
|
|
</head>
|
||
|
|
<body>
|
||
|
|
|
||
|
|
|
||
|
|
<div id="header">
|
||
|
|
|
||
|
|
|
||
|
|
<a href="http://students.cs.byu.edu/~cs235headta/index.php"><img src="./lab04_files/title.png" alt="Computer Science 235" class="centered" border="0" height="77"></a>
|
||
|
|
</div>
|
||
|
|
|
||
|
|
<div id="sidebar">
|
||
|
|
<div id="menu">
|
||
|
|
<h2>Information</h2>
|
||
|
|
<ul>
|
||
|
|
<li><a href="http://students.cs.byu.edu/~cs235headta/index.php">Announcements</a></li>
|
||
|
|
<li><a href="http://students.cs.byu.edu/~cs235headta/information/ta_schedule.php">TA Schedule</a></li>
|
||
|
|
<li><a href="http://students.cs.byu.edu/~cs235headta/information/personnel.php">Personnel</a></li>
|
||
|
|
<li><a href="http://students.cs.byu.edu/~cs235headta/information/view_grades.php">View Grades</a></li>
|
||
|
|
<li><a href="http://students.cs.byu.edu/~cs235headta/information/syllabus.php">Syllabus</a></li>
|
||
|
|
<li><a href="http://students.cs.byu.edu/~cs235headta/homework/labs.php?lab=0">Orientation</a></li>
|
||
|
|
</ul>
|
||
|
|
</div>
|
||
|
|
|
||
|
|
<div id="menu">
|
||
|
|
<h2>Homework</h2>
|
||
|
|
<ul>
|
||
|
|
<li><a href="http://students.cs.byu.edu/~cs235headta/homework/labs.php?lab=1">Labs</a></li>
|
||
|
|
<li><a href="http://students.cs.byu.edu/~cs235headta/homework/course_schedule.php">Course Schedule</a></li>
|
||
|
|
<li><a href="http://students.cs.byu.edu/~cs235headta/homework/cover_sheets.php">Cover Sheets</a></li>
|
||
|
|
<li><a href="http://students.cs.byu.edu/~cs235headta/homework/submit_exam.php">Submit Exam</a></li>
|
||
|
|
<li><a href="http://students.cs.byu.edu/~cs235headta/homework/help_passoff.php">Help / Passoff</a></li>
|
||
|
|
</ul>
|
||
|
|
</div>
|
||
|
|
|
||
|
|
<div id="menu">
|
||
|
|
<h2>Reference</h2>
|
||
|
|
<ul>
|
||
|
|
<li><a href="http://students.cs.byu.edu/~cs235headta/reference/lecture_slides.php">Lecture Slides</a></li>
|
||
|
|
<li><a href="http://students.cs.byu.edu/~cs235headta/reference/book_examples.php">Book Examples</a></li>
|
||
|
|
<li><a href="http://students.cs.byu.edu/~cs235headta/reference/vs_guide.php">Visual Studio Guide</a></li>
|
||
|
|
<li><a href="http://students.cs.byu.edu/~cs235headta/reference/eclipse_guide.php">Eclipse/Linux Guide</a></li>
|
||
|
|
<li><a href="http://students.cs.byu.edu/~cs235headta/reference/msdn.php">MSDN Academic Alliance</a></li>
|
||
|
|
<li><a href="http://students.cs.byu.edu/~cs235headta/reference/exam_guide.php">Exam Guide</a></li>
|
||
|
|
<li><a href="http://www.cplusplus.com/reference/">C++ Reference</a></li>
|
||
|
|
<li><a href="http://students.cs.byu.edu/~cs235headta/reference/javacpp.php">Java vs. C++</a></li>
|
||
|
|
|
||
|
|
</ul>
|
||
|
|
</div>
|
||
|
|
|
||
|
|
<div id="menu">
|
||
|
|
<h2>Software</h2>
|
||
|
|
<ul>
|
||
|
|
<li><a href="http://www.microsoft.com/visualstudio/en-us/products/2010-editions/visual-cpp-express"> Visual Studio</a>
|
||
|
|
</li></ul>
|
||
|
|
</div>
|
||
|
|
</div>
|
||
|
|
|
||
|
|
<div id="page">
|
||
|
|
<div id="content">
|
||
|
|
|
||
|
|
<script type="text/javascript">
|
||
|
|
function redirectLab(lab) {
|
||
|
|
window.location = "labs.php?lab=" + lab;
|
||
|
|
}
|
||
|
|
|
||
|
|
</script>
|
||
|
|
|
||
|
|
<h2>Lab 4</h2>
|
||
|
|
<form action="" method="get" name="changeLab">
|
||
|
|
<select name="lab" onchange="redirectLab(document.changeLab.lab.value);">
|
||
|
|
<option value="0" selected="">Select a Lab:</option>
|
||
|
|
<option value="0">Orientation</option>
|
||
|
|
<option value="1">Lab 1</option>
|
||
|
|
<option value="2">Lab 2</option>
|
||
|
|
<option value="3">Lab 3</option>
|
||
|
|
<option value="4" selected="selected">Lab 4</option>
|
||
|
|
<option value="5">Lab 5</option>
|
||
|
|
<option value="6">Lab 6</option>
|
||
|
|
<option value="7">Lab 7</option>
|
||
|
|
<option value="8">Lab 8</option>
|
||
|
|
<option value="9">Lab 9</option>
|
||
|
|
<option value="10">Lab 10</option>
|
||
|
|
</select>
|
||
|
|
</form>
|
||
|
|
|
||
|
|
|
||
|
|
<div class="infoBox">
|
||
|
|
<h3>Purpose</h3>
|
||
|
|
<p>To become familiarized with the use of stacks as data structures.</p>
|
||
|
|
|
||
|
|
<h3>Key Reading</h3>
|
||
|
|
<ul>
|
||
|
|
<li>5.1-5.4</li>
|
||
|
|
</ul>
|
||
|
|
|
||
|
|
<h3>Background</h3>
|
||
|
|
<p>Develop an Expression Manager that performs several operations on infix and postfix expressions. Be able to convert from one form to the other, evaluate postfix expressions, and check for balanced parenthetical expressions.</p>
|
||
|
|
|
||
|
|
|
||
|
|
<p>You may also refer to Edsger Dijkstra's "Shunting-yard algorithm" for additional help, which can be viewed <a href="http://en.wikipedia.org/wiki/Shunting_yard_algorithm" target="_blank">here</a>.</p>
|
||
|
|
<h3>Requirements</h3>
|
||
|
|
|
||
|
|
<p>You will need <a href="http://students.cs.byu.edu/~cs235headta/homework/student_files/Lab3ShuntingYard.zip">these files</a> to complete the assignment. Details for method constraints are found in these documents and are still a part of the requirements. (If downloaded before 9/17, 2:00 pm re-download. There are errors that were fixed that will cause the driver to break on working code.)</p>
|
||
|
|
|
||
|
|
|
||
|
|
<p>Extend the <code>ExpressionManagerInterface.h</code>.</p>
|
||
|
|
<p></p>
|
||
|
|
<h4>Part 1 - Balanced Symbols Check (10 points)</h4>
|
||
|
|
<ul>
|
||
|
|
<li>Determine and report whether an expression is balanced. { [ } ] is not balanced. [ ( ) ] is balanced and valid</li>
|
||
|
|
</ul>
|
||
|
|
<h4>Part 2 - Infix to Postfix Conversion (10 points)</h4>
|
||
|
|
<ul>
|
||
|
|
<li>Alert the user if the given infix expression is not valid</li>
|
||
|
|
<li>Convert the infix expression into a postfix expression and display the postfix expression</li>
|
||
|
|
</ul>
|
||
|
|
<h4>Part 3 - Postfix to Infix Conversion (10 points)</h4>
|
||
|
|
<ul>
|
||
|
|
<li>Alert the user if the given postfix expression is not valid</li>
|
||
|
|
<li>Convert the postfix expression into an infix expression and display the infix expression</li>
|
||
|
|
</ul>
|
||
|
|
<h4>Part 4 - Postfix Expression Evaluation (10 points)</h4>
|
||
|
|
<ul>
|
||
|
|
<li>Alert the user if the given postfix expression is not valid</li>
|
||
|
|
<li>Evaluate the given postfix expression and display the result</li>
|
||
|
|
<li>Handle attempts to divide by 0</li>
|
||
|
|
</ul>
|
||
|
|
|
||
|
|
<h3>Requirement Notes</h3>
|
||
|
|
|
||
|
|
<h4>General</h4>
|
||
|
|
<ul>
|
||
|
|
<li>Valid expressions consist of integers; brackets, braces, and parentheses; and +, -, *, /, and %. Reject any invalid expressions and inform the user.</li>
|
||
|
|
<li>Your calculations should perform integer divison and produce integer results</li>
|
||
|
|
<li>Valid expressions also need to satisfy standard infix or postfix requirements</li>
|
||
|
|
<li>{,},(,),[, and ] are the only symbols considered for the Balanced Symbols Check</li>
|
||
|
|
<li>Your program should allow the user to repeat the activities</li>
|
||
|
|
<li>You can assume there will be a space between every number or operator</li>
|
||
|
|
<li>You must put parenthesis '()' around every part of the expression during the postfix to infix conversion. i.e. "4 2 5 + *" = "( 4 *( 2 + 5 ) )"</li>
|
||
|
|
<li>You must use the stack class pre-defined in the C++ Standard Template Library (STL). i.e. <code>#include <stack></code></li>
|
||
|
|
</ul>
|
||
|
|
|
||
|
|
<h4>Test Cases</h4>
|
||
|
|
<ul>
|
||
|
|
<li>The expressions in the test files will be written with one complete expression on each line. Available below are small test files you may use to test your program for pass off on each part.
|
||
|
|
This is not a comprehensive set of tests, but it should familiarize you with the format and give you ideas for additional test cases you can add. Your program must display the result of the selected
|
||
|
|
operation for each of the expressions in the file.
|
||
|
|
<ul>
|
||
|
|
<li><a href="http://students.cs.byu.edu/~cs235headta/homework/student_files/part1.txt">Part1.txt</a></li>
|
||
|
|
<li><a href="http://students.cs.byu.edu/~cs235headta/homework/student_files/part2.txt">Part2.txt</a></li>
|
||
|
|
<li><a href="http://students.cs.byu.edu/~cs235headta/homework/student_files/part3.txt">Part3.txt</a></li>
|
||
|
|
<li><a href="http://students.cs.byu.edu/~cs235headta/homework/student_files/part4.txt">Part4.txt</a></li>
|
||
|
|
</ul>
|
||
|
|
</li>
|
||
|
|
</ul>
|
||
|
|
</div> </div>
|
||
|
|
</div>
|
||
|
|
</body><link rel="stylesheet" type="text/css" href="data:text/css,"></html>
|