Class Notes (811,703)
CSC148H1 (92)
Paul Gries (18)
Lecture

# jan18c.docx

2 Pages
111 Views

Department
Computer Science
Course
CSC148H1
Professor
Paul Gries
Semester
Winter

Description
 ((3 + 4) – (7 – 1)) o simply (3 + 4)  place all digits on stack *‘(‘, ‘3’, ‘4] o once reach ‘)’, evaluate the expression  assigned values to variablev1 = ‘4’, op: ‘+’, v2 = ‘3’  int(v2) + int(v1)  solving problem  solve by testing on paper, start w/ simpler example 1. def eval_expr(expr): 2. for ch in expr: #everytime hit close paranthese, eval till open paranthes 3. stk = Stack() 4. for char in expr: 5. if ch in '(1234567890+-*/': 6. stk.push(char) 7. elif char = „)‟: 8. v1 = stk.pop() 9. op = stk.pop() 10. v2 = stk.pop() 11. stk.pop() 12. stk.push(evaluate1(v2,op,v1)) 13. return st.pop() 14. 15. def evaluate1(v2, op, v1): 16. v1, v2 = int(v1), int(v2) 17. if op == „+‟: 18. return v2 + v1 19. elif op == „-‟: 20. return v2 - v1 21. elif op == „*‟: 22. return v2 * v1 23. elif op == „/‟: 24. return v2 / v1 25. 26. def evaluate2(v2, op, v1): 27. return eval(v2 + op + v1)  Stack Implementation choices: o Ex. stack.py (constant time operation) vs. bad_stack.py (linear operation) o bad_stack pushes item on a list at index 0, instead of stacking it at the end  runtime increases w/ longer lists 1. class Bad_Stack(object): 2. '''A last-in, first-out (LIFO) stack of items''' 3. 4. def __init__(self): 5. '''(Stack) -> None 6. A new empty Stack.''' 7. 8. self.contents = [] 9. 10. def pop(self): 11. '''(Stack) -> object 12. Remove and return the top item.''' 13. 14. return self.contents.pop(0) 15. 16. def is_empty(self): 17. '''(Stack) -> bool 18. Return whether the stack is empty.''' 19. 20. return not self.contents 21. 22. def push(self, o): 23. '''(Stack, object) -> None 24. Place o on top of the stack.''' 25. 26. self.contents.insert(0, o) o compare time, longer list bad_stack completion time longer EXCEPTIONS  stck.pop() when stack.is_empty() o We wrote the Stack class so that other programmers (including us) could use it. o There are two kinds of people who are involved with every function and class:
More Less

Related notes for CSC148H1
Me

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.