2023年11月25日

算法设计代写 | COSC 2123/1285 Assignment 2: Algorithm Design & Complexity Analysis

本次美国代写是Java数据结构算法的一个Programming Assignment

In this assignment, you will use stacks and queues to check documents for correct nesting. After
briefly explaining how this can be used as part of the syntax validation in multiple settings including
arithmetic expressions and computer programming languages, you will build a function that applies
this knowledge to check simple HTML files for valid tag nesting.

Learning Objectives

In completing this assignment, you will:

• Become familiar with the methods in the java.util.Stack class and java.util.Queue interface

• Work with an abstract data type (specifically, queues) by using only the interface of an im-
plementation

• Apply what you have learned about how stacks and queues work

Background

Consider the following valid Python expression:

1 [0, (1, 2, {3, (4, 5, 6) , (7, 8)}, 9) , 10, 11, 12 ]

The expression contains 3 types of open and close elements:

There are two rules:

1. A closing element must close the current context

2. At the end of input, all contexts must be closed

An open element starts a context and the complimentary close element ends that context. Note
from the above example that contexts can be nested inside each other, but we can’t close an outer
context until the current context is closed, so this expression would be invalid:

1 [0, (1, 2, {3, (4, 5, 6) , (7, 8}) , 9) , 10, 11, 12 ]

Now suppose we want to create a syntax checking algorithm that reads a source code file and
determines if the above two rules are respected. Given a parser that converts the source code into
a queue of opening and closing elements, we then repeatedly dequeue elements. For each opening
element we dequeue, we push it to a stack. For each closing element we dequeue, we pop that stack
only if the top of the stack matches the dequeued element; if the top of the stack doesn’t match,
we know there must be a syntax error. Finally, we know the entire file is valid if, upon emptying
our queue, we find that our stack is empty.

Try this yourself using a few simple examples.

HTML

Once you understand how the above algorithm works, you will be ready to tackle this assignment.
Web pages are written in Hypertext Markup Language (HTML). An HTML file is composed of text
surrounded by tags, where the tags “markup” the text by specifying its format, layout, or other
information. Tags, like the opening and closing elements we saw in the previous section, can be
nested as well.

Here is a simple example:

1 <html >
2 <head ><title >Sample HTML page </ title ></ head >
3 <body >
4 This is some <b>HTML text !</b>
5 </ body >
6 </ html >

The exact meanings of the tags are not important, and you do not need to fully understand or
learn about HTML for this assignment. Just know that tags such as <body> and <b> are known
as “open tags” because they indicate the start of some formatting, and tags such as </body> (with
the forward slash before the word) are known as “close” tags because they indicate the end of the
formatting.

In theory (though not often in practice), well formatted HTML requires that the tags are “balanced,”
i.e. that open tags are matched by their corresponding close tag in the correct order.

For instance, if we ignore whitespace and the text between the tags, we end up with this:

1 <html ><head ><title ></ title ></ head ><body ><b></b></ body ></ html >

Note that there is some symmetry in the HTML tags, in that whenever we close a tag, it matches
the most recent (unclosed) open tag.

For instance, notice that the “title” closing tag matches the most recently opened tag:

1 <html ><head ><title ></ title ></ head ><body ><b></b></ body ></ html >

And in this case, the closing “body” tag matches the open “body” tag, which is the most recently
opened tag that has not yet been closed (since the “b” tag is already closed):

1 <html ><head ><title ></ title ></ head ><body ><b></b></ body ></ html >

A peculiarity of HTML is that some tags are called “self-closing” and do not rely on a matching
closing tag. For instance, here the “br” tag closes itself:

1 <html ><head >head ><body ><b><br/></b></ body ></ html >

A self-closing tag is one that ends with the forward slash character, as opposed to a closing tag,
which starts with one. You can think of a self-closing tag as one that has a “neutral” effect on the
current context; it neither creates a new context nor closes an existing one. Equivalently, you could
think of it as creating a new context and instantaneously closing that context.

It is easy to make mistakes in HTML code! Most commonly, people forget to close tags or close
nested tags in the wrong order, e.g. something like this:

1 <html ><head ><title ></ title ><body ><b></ body ></b></ html >

In this case, there is no close “head” tag, and the “body” tag is closed in the wrong order: it should
come after the close “b” tag.

In this assignment, you will write a method that determines whether an HTML file is well formatted
using a stack. Every time your code encounters an open tag, it should push it onto the stack; when
it encounters a close tag, it should pop the tag off the top of the stack, and if they don’t match,
then you’ll know the file is not well formatted. More examples and explanation are provided below.