Đã hoàn thành

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"

Kĩ năng: Lập trình C, Kĩ thuật, Linux, MySQL, PHP, Kiến trúc phần mềm, Kiểm tra phần mềm

Xem nhiều hơn: 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

Về Bên Thuê:
( 16 nhận xét ) United States

ID dự án: #2924648

Được trao cho:

vw767279vw

See private message.

$21.25 USD trong 14 ngày
(17 Đánh Giá)
2.7

18 freelancer đang chào giá trung bình $50 cho công việc này

finecodervw

See private message.

$34 USD trong 14 ngày
(145 Nhận xét)
6.0
DanD

See private message.

$51 USD trong 14 ngày
(212 Nhận xét)
5.8
ExpertFromInd

See private message.

$42.5 USD trong 14 ngày
(48 Nhận xét)
5.4
ingeniadesign

See private message.

$55.25 USD trong 14 ngày
(53 Nhận xét)
5.1
herculesevw

See private message.

$55.25 USD trong 14 ngày
(79 Nhận xét)
4.7
antosgroup

See private message.

$17 USD trong 14 ngày
(27 Nhận xét)
4.6
lalesculiviu

See private message.

$85 USD trong 14 ngày
(18 Nhận xét)
4.2
jaffersonso

See private message.

$38.25 USD trong 14 ngày
(16 Nhận xét)
3.9
teamvw

See private message.

$25.5 USD trong 14 ngày
(35 Nhận xét)
3.8
cossimin

See private message.

$63.75 USD trong 14 ngày
(18 Nhận xét)
3.5
compwizvw

See private message.

$85 USD trong 14 ngày
(8 Nhận xét)
3.2
patrica

See private message.

$74.8 USD trong 14 ngày
(18 Nhận xét)
3.2
pawanvw

See private message.

$85 USD trong 14 ngày
(5 Nhận xét)
2.2
cavw

See private message.

$6.8 USD trong 14 ngày
(0 Nhận xét)
0.0
balalay

See private message.

$59.5 USD trong 14 ngày
(0 Nhận xét)
0.0
stefansimon

See private message.

$8.5 USD trong 14 ngày
(1 Nhận xét)
0.0
vw796350vw

See private message.

$85 USD trong 14 ngày
(0 Nhận xét)
0.0