Lengkap

Stack Tree

* Using Microsoft Visual C++, Write a program that takes as input a fully parenthesized arithmetic expression and converts it to a binary expression tree. Your program should display the tree in some way and also print the value associated with the root. Allow for the leaves to store variables of the form x1, x2, x3, and so on, which are initially 0 and which can be updated interactively by your program, with the corresponding update in the printed value of the root of the expression tree. * For details, please read deliverables. Comment : Try to make the program as simple as possible in the way of coding. I mean "simple" as coding the program not so complicated so that I can understand the algorithm of the program.

## Deliverables

The arithmetic expression consists of: Numbers. All numbers are integer. Variables. In the format of x1, x2, x3 ...... Parentheses. They have their usual meaning. Only ( and ) will be used; don't use { } [ ]. + for addition; used only as a binary operator. - for subtraction; used only as a binary operator. * for multiplication. / for division. ===Input format=== Take the input from standard input, and the length of expression is limited to one line. For easy string tokenize of the input expression, separate the operator, operand, and parenthesis by at least one space. All variables are inputted in one line, follow the expression, with the order of x1, x2, x3 ...... For example, input expression: ( x1 + 2 ) * 4 + x2 * ( 12 - x3 / x4 ) input variables: 3 2 6 3 ===Output format=== Output the tree in the format you like. Output the prefix expression (preorder traversal of the tree). Output the final value of the expression. For the above example, output: + * + x1 2 4 * x2 - 12 / x3 x4 40 ===Expression evaluation algorithm=== You need two stacks, a operand stack (to hold the numbers and variables), and an operator stack (to hold the operators). Numbers will be int values, operators will be char values. The algorithm is roughly as follows. Note that no error checking is done explicitly. While there are still tokens to be read in, Get the next token. If the token is: A number: push it onto the operand stack. A variable: get its value, and push its value onto the operand stack. A left parenthesis: push it onto the operator stack. A right parenthesis: While the thing on top of the operator stack is not a left parenthesis, Pop the operator from the operator stack. Pop the operand stack twice, getting two operands. Apply the operator to the operands, in the correct order. Push the result onto the operand stack. Pop the left parenthesis from the operator stack, and discard it. An operator (call it thisOp): While the operator stack is not empty, and the top thing on the operator stack has the same or greater precedence as thisOp, Pop the operator from the operator stack. Pop the operand stack twice, getting two operands. Apply the operator to the operands, in the correct order. Push the result onto the operand stack. Push thisOp onto the operator stack. While the operator stack is not empty, Pop the operator from the operator stack. Pop the operand stack twice, getting two operands. Apply the operator to the operands, in the correct order. Push the result onto the operand stack. At this point the operator stack should be empty, and the operand stack should have only one value in it, which is the final result. ===Tree construction=== Create a node for each number, variable, and operator. Store the pointer to the node in the operator stack and operand stack. When applying the operator to the two operands, modify the left pointer and right pointer of the operator node, let them point to the nodes hold the two operands.

## Platform

"Linux" and possibly "Microsoft Visual C++ 6.0 in Windows"

Kemahiran: Pengaturcaraan C, Kejuruteraan, Linux, MySQL, PHP, Kejuruteraan Perisian, Ujian Perisian

Lihat lagi: variables in programming, variable programming, tree update, tree programming, tree prefix, tree node, tree in order, tree in algorithm, string prefix, string algorithm, stacks and stacks, stack programming, simple binary tree, simple binary division, simple algorithm example, push algorithm, programming variable, programming tree, programming operators, programming operator

Tentang Majikan:
( 16 ulasan ) United States

ID Projek: #2924648

Dianugerahkan kepada:

vw767279vw

See private message.

$21.25 USD dalam 14 hari
(17 Ulasan)
2.7

18 pekerja bebas membida secara purata $50 untuk pekerjaan ini

finecodervw

See private message.

$34 USD dalam 14 hari
(145 Ulasan)
6.0
DanD

See private message.

$51 USD dalam 14 hari
(212 Ulasan)
5.8
ExpertFromInd

See private message.

$42.5 USD dalam 14 hari
(48 Ulasan)
5.4
ingeniadesign

See private message.

$55.25 USD dalam 14 hari
(53 Ulasan)
5.1
herculesevw

See private message.

$55.25 USD dalam 14 hari
(79 Ulasan)
4.7
antosgroup

See private message.

$17 USD dalam 14 hari
(27 Ulasan)
4.6
lalesculiviu

See private message.

$85 USD dalam 14 hari
(18 Ulasan)
4.2
jaffersonso

See private message.

$38.25 USD dalam 14 hari
(16 Ulasan)
3.9
teamvw

See private message.

$25.5 USD dalam 14 hari
(35 Ulasan)
3.8
cossimin

See private message.

$63.75 USD dalam 14 hari
(18 Ulasan)
3.5
compwizvw

See private message.

$85 USD dalam 14 hari
(8 Ulasan)
3.2
patrica

See private message.

$74.8 USD dalam 14 hari
(18 Ulasan)
3.2
pawanvw

See private message.

$85 USD dalam 14 hari
(5 Ulasan)
2.2
cavw

See private message.

$6.8 USD dalam 14 hari
(0 Ulasan)
0.0
balalay

See private message.

$59.5 USD dalam 14 hari
(0 Ulasan)
0.0
stefansimon

See private message.

$8.5 USD dalam 14 hari
(1 Ulasan)
0.0
vw796350vw

See private message.

$85 USD dalam 14 hari
(0 Ulasan)
0.0