MUST BE DONE IN PYTHON Your program can parse a valid expression into a binary t

Question

MUST BE DONE IN PYTHON

Your program can parse a valid expression into a binary tree and calculate the final result. [2pts] For example, given the input string: (((2*(3+2))+5)/2) The calculated result will be 7.5 Note that this example is for illustrative purposes, and during the marking process you may be given a different string to test your solution.

2. Your program can visualise the generated binary tree. [3pts] The expected output tree for the input shown under (1) above is as follows (you can print it on the screen, and you don’t need to print the lines connecting the tree nodes if it is not convenient):

/

+ 2

* 5

2 +

3 2

3. Your program can save the binary tree into a file. After you quit your program, you can restart your program and reload the tree from the same file into memory and visualise it again. [2pts]

Hint: You may consider using the pickle package for serialisation. You may also use other packages or could write your own functions for serialisation.

4. Your program should be able to report an error message if an input string is not a valid one. [2pts]

Specifically, your program should report an error message “not a valid expression” for each of the following invalid expressions

(4*3*2) “three operands within one pair of brackets”

(4*(2)) “only one operand within one pair of brackets”

(4*(3+2)*(2+1)) “three operands within one pair of brackets”

(2*4)*(3+2) “no outer brackets”

((2+3)*(4*5) “bracket missing”

(2+5)*(4/(2+2))) “bracket missing”

(((2+3)*(4*5))+(1(2+3))) “operator missing between

1(2+3)”

Note: To be awarded marks for this task, you don’t need to report the exact error messages for the above expressions; reporting “not a valid expression” will be sufficient.

5. Further to Task 4, your program can additionally report why the expression is not valid. [1pt] The following expressions would have the corresponding error messages as shown:

(4*3*2) Not a valid expression, wrong number of operands.

(4*(2)) Not a valid expression, wrong number of operands.

(4*(3+2)*(2+1)) Not a valid expression, wrong number of operands.

(2*4)*(3+2) Not a valid expression, brackets mismatched.

((2+3)*(4*5) Not a valid expression, brackets mismatched.

(2+5)*(4/(2+2))) Not a valid expression, bracket mismatched.

(((2+3)*(4*5))+(1(2+3))) Not a valid expression, operator missing.

Final Notes You should document your code well so that not only your code is well written, but also your idea and detailed steps are provided along with the code. Poorly documented code may result in a lower mark

Explanation / Answer

Here is my code to evaluate the expression

------------------------------------------------------------------------------------------------------------------

#method to evaluate the expression passed as a string
def evaluateExpression(expression):
#converting string into list
expression = list(expression)
#creating a stack to operate upon
stack = list()
num = ""
#while loop to push the operators and operands into the stack
#and at the same time popping it from the list
while len(expression) > 0:
#extracting a token at position 0
c = expression.pop(0)
#if c is a number then append it to num else append to stack
if c in "0123456789.":
num =num + c
else:
if num != "":
stack.append(num)
num = ""
if c in "+-*/":
stack.append(c)
elif c == ")":
num2 = stack.pop()
op = stack.pop()
num1 = stack.pop()
#performing the calculations depending upon the operators
if op == "+":
stack.append(str(float(num1) + float(num2)))
elif op == "-":
stack.append(str(float(num1) - float(num2)))
elif op == "*":
stack.append(str(float(num1) * float(num2)))
elif op == "/":
stack.append(str(float(num1) / float(num2)))
return stack.pop()

expr = "(((2*(3+2))+5)/2)"
print expr
print evaluateExpression(expr)

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.