{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cp\u003eYou are enrolled in the Computer Organization and\n Architecture course at your university. You decide to write a\n program to help check your work by computing the output value\n of a combinational digital circuit, given its inputs.\u003c/p\u003e\n \u003cdiv id\u003d\"circuitmath:1\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/ecdefacde026d12b5944a1028fb06c69?v\u003d1715879470\" alt\u003d\"\\includegraphics[width\u003d0.4\\textwidth ]{example_circuit}\" style\u003d\"width:40.00%\"\u003e\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 1\u003c/b\u003e: An example of a combinational digital\n circuit. See the text for an explanation.\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n \u003cp\u003eConsider the circuit shown in Figure\u0026nbsp;1, which we use\n for illustration. This circuit has four inputs (letters A\n through D on the left), each of which is either true or false.\n There are four ‘gates’ each of which is one of three types:\n AND, OR, or NOT. Each gate produces either a true or false\n value, depending on its inputs. The last gate (the OR on the\n right) produces the output of the entire circuit. We can write\n these three types of gates in text by their equivalent\n \u003cem\u003elogical operators\u003c/em\u003e: \u003ctt\u003e*\u003c/tt\u003e for AND, \u003ctt\u003e+\u003c/tt\u003e for\n OR, and \u003ctt\u003e-\u003c/tt\u003e for NOT. In what follows, we’ll use the\n operators rather than gates to describe circuits.\u003c/p\u003e\n \u003cp\u003eHere is how these operators work. Given an assignment of\n true (\u003ctt\u003eT\u003c/tt\u003e) or false (\u003ctt\u003eF\u003c/tt\u003e) for each input, the\n operators produce the truth value indicated in the following\n tables:\u003c/p\u003e\n \u003ccenter\u003e\n \u003ctable cellspacing\u003d\"0\" class\u003d\"tabular\"\u003e\n \u003ctbody\u003e\u003ctr\u003e\n \u003ctd style\u003d\"border-top-style:solid; border-left:1px solid black; border-right:1px solid black; border-top-color:black; border-top-width:1px; text-align:center\"\u003e\n \u003cp\u003e\u003ctt\u003eA\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:center; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eB\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:center; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eA B *\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:center; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eA B +\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"border-top-style:solid; border-left:1px solid black; border-right:1px solid black; border-top-color:black; border-top-width:1px; text-align:center\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:center; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:center; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:center; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"text-align:center; border-right:1px solid black; border-left:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:center; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:center; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:center; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"text-align:center; border-right:1px solid black; border-left:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:center; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:center; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:center; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"border-bottom-style:solid; border-bottom-width:1px; border-left:1px solid black; border-right:1px solid black; text-align:center; border-bottom-color:black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-bottom-color:black; border-bottom-width:1px; text-align:center; border-bottom-style:solid; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-bottom-color:black; border-bottom-width:1px; text-align:center; border-bottom-style:solid; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-bottom-color:black; border-bottom-width:1px; text-align:center; border-bottom-style:solid; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\u003c/table\u003e \n \u003ctable cellspacing\u003d\"0\" class\u003d\"tabular\"\u003e\n \u003ctbody\u003e\u003ctr\u003e\n \u003ctd style\u003d\"border-top-style:solid; border-left:1px solid black; border-right:1px solid black; border-top-color:black; border-top-width:1px; text-align:center\"\u003e\n \u003cp\u003e\u003ctt\u003eA\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:center; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eA -\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"border-top-style:solid; border-left:1px solid black; border-right:1px solid black; border-top-color:black; border-top-width:1px; text-align:center\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:center; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"border-bottom-style:solid; border-bottom-width:1px; border-left:1px solid black; border-right:1px solid black; text-align:center; border-bottom-color:black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-bottom-color:black; border-bottom-width:1px; text-align:center; border-bottom-style:solid; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\u003c/table\u003e\n \u003c/center\u003e\n \u003cp\u003eNotice that AND and OR take two inputs, whereas NOT operates\n on only one input. Also, we use \u003cem\u003epostfix notation\u003c/em\u003e to\n write expressions involving operators (like \u003cspan class\u003d\"tex2jax_process\"\u003e$\\verb|A B *|$\u003c/span\u003e), where the operator\n comes \u003cem\u003eafter\u003c/em\u003e its input(s) (just as how in\n Figure\u0026nbsp;1, each gate in the circuit diagram comes after its\n inputs).\u003c/p\u003e\n \u003cp\u003eWhen we describe a valid circuit in postfix notation, we use\n the following syntax.\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eAn uppercase letter (\u003ctt\u003eA\u003c/tt\u003e through \u003ctt\u003eZ\u003c/tt\u003e) is a\n valid circuit. In other words, an input alone (without any\n gates) is a valid circuit (which produces as output its own\n input value).\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eIf \u003ctt\u003e\u0026lt;C1\u0026gt;\u003c/tt\u003e and \u003ctt\u003e\u0026lt;C2\u0026gt;\u003c/tt\u003e are valid\n circuits, then ‘\u003ctt\u003e\u0026lt;C1\u0026gt; \u0026lt;C2\u0026gt; *\u003c/tt\u003e’ is a\n valid circuit that produces the AND of the outputs of the\n two subcircuits.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eIf \u003ctt\u003e\u0026lt;C1\u0026gt;\u003c/tt\u003e and \u003ctt\u003e\u0026lt;C2\u0026gt;\u003c/tt\u003e are valid\n circuits, then ‘\u003ctt\u003e\u0026lt;C1\u0026gt; \u0026lt;C2\u0026gt; +\u003c/tt\u003e’ is a\n valid circuit that produces the OR of the outputs of the\n two subcircuits.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eIf \u003ctt\u003e\u0026lt;C1\u0026gt;\u003c/tt\u003e is a valid circuit, then\n ‘\u003ctt\u003e\u0026lt;C1\u0026gt; -\u003c/tt\u003e’ is a valid circuit that produces\n the NOT of \u003ctt\u003e\u0026lt;C1\u0026gt;\u003c/tt\u003e’s output.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003cp\u003eNo other description is a valid circuit.\u003c/p\u003e\n \u003cp\u003eThus, one of the ways the circuit in Figure 1 could be\n described using postfix notation is as the string:\u003c/p\u003e\n \u003ccenter\u003e\n \u003ctt\u003eA B * C D + - +\u003c/tt\u003e\n \u003c/center\u003e\n \u003cp\u003eGiven a truth value (\u003ctt\u003eT\u003c/tt\u003e or \u003ctt\u003eF\u003c/tt\u003e) for each of\n the inputs (\u003ctt\u003eA\u003c/tt\u003e, \u003ctt\u003eB\u003c/tt\u003e, \u003ctt\u003eC\u003c/tt\u003e, and \u003ctt\u003eD\u003c/tt\u003e\n in this example), their values propagate through the gates of\n the circuit, and the truth value produced by the last gate is\n the output of the circuit. For example, when the above circuit\n is given inputs \u003ctt\u003eA\u003dT\u003c/tt\u003e, \u003ctt\u003eB\u003dF\u003c/tt\u003e, \u003ctt\u003eC\u003dT\u003c/tt\u003e,\n \u003ctt\u003eD\u003dF\u003c/tt\u003e, the output of the circuit is \u003ctt\u003eF\u003c/tt\u003e.\u003c/p\u003e\n \u003cp\u003eGiven an assignment to variables and a circuit description,\n your software should print the output of the circuit.\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe first line of the input consists of a single integer\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e, satisfying\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq n \\leq 26$\u003c/span\u003e,\n denoting the number of input variables. Then follows a line\n with \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e space-separated\n characters. Each character is either \u003cspan class\u003d\"tex2jax_process\"\u003e$\\verb|T|$\u003c/span\u003e or \u003cspan class\u003d\"tex2jax_process\"\u003e$\\verb|F|$\u003c/span\u003e, with the \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003eth such character indicating the\n truth value of the input that is labeled with the \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003eth letter of the alphabet.\u003c/p\u003e\n \u003cp\u003eThe last line of input contains a circuit description, which\n obeys the syntax described above. Each circuit is valid, uses\n only the first \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e letters\n of the alphabet as input labels, and contains at least\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e and at most\n \u003cspan class\u003d\"tex2jax_process\"\u003e$250$\u003c/span\u003e total non-space\n characters.\u003c/p\u003e\n \u003cp\u003eNote that while each variable is provided only one truth\n value, a variable may appear multiple times in the circuit\n description and serve as input to more than one gate.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003ePrint a single character, the output of the circuit (either\n \u003ctt\u003eT\u003c/tt\u003e or \u003ctt\u003eF\u003c/tt\u003e), when evaluated using the given input\n values.\u003c/p\u003e\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\nT F T F\nA B * C D + - +\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eF\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}