Help with Python: Implementing Algorithm

  • Python
  • Thread starter FallArk
  • Start date
  • Tags
    Python
In summary: Well, from what I understand, you can't actually call the function "eval_infix" with parameters, you can only pass in a list of expressions. In order to call the function with a parameter, you would have to create a function that takes in an expression and returns the corresponding parameter.
  • #1
FallArk
127
0
My instructor gave out a sample code as listed below:
Code:
def eval_infix_sum(expr, pos):
   """evaluate a sum expression (zero or more additions and subtractions)
      expr      Python string list           complete expression to be evaluated
      pos       integer                          subscript to current token
   """
       ... implementation of algorithm above

       return ans, pos                     # return result and updated subscript

def   eval_infix_product(expr, pos):
   """evaluate a product expression (zero or more multiplications/divisions)

# NOTE:   This must be extended to support parenthesized sub-expressions)
def  eval_infix_factor( expr, pos ):
   """evaluate a factor (number or parenthesized sub-expression)

      return int(expr[pos]), pos+1        # convert string to int, and move past

#  the following functions are defined to supply a 'friendlier' interface to the clients,
# which will later also be used to provide some degree of implementation hiding.

def eval_infix_list(expr):
   """evaluate an expression represented as a list of strings
     ans, discard = eval_infix_sum( expr, 0 )     # start subscript at 0, then forget it
     return ans

def eval_infix(expr):
   """evaluate an expression represented as a single space-separated string
     return eval_infix_list(expr.split() + [ ";"])    # make a list, and append semicolon
What I have to do is to implement the algorithm. My instructor did not mention any basics of python in class other than telling me
Code:
def
starts a function. The way I was thinking about implementing this algorithm is that when given something like
Code:
eval_infix_product( [ "2","*","3",";" ], 0)
, the function
eval_infix_product
will check each element inside the list and decide if it is a division or multiplication, however, I do not really know how to write this in python. Could someone explain this and help me?
 
Technology news on Phys.org
  • #2
I tried to make one of the functions work by doing this:
Code:
def eval_infix_sum(expr,pos):
    if expr[pos+1] == '+' :
        ans = expr[pos] + expr[pos+2]
    elif expr[pos+1] == '-' :
        ans = expr[pos] - expr[pos+2]
    pos = pos + 1
    return ans,pos
My intention is trying to let the program move forward through the data and figure out what to do, but since the input in this case is always a list, addition will just display "2 + 3" as "23", is there any work around?
 
  • #3
Update:
I figured out how to make the output an integer. By doing this:
Code:
def eval_infix_sum(expr,pos):
    if expr[pos+1] == '+' :
        ans = int(expr[pos]) + int(expr[pos+2])
    elif expr[pos+1] == '-' :
        ans = int(expr[pos]) - int(expr[pos+2])
    pos = pos + 1
    return ans,pos
But I am still confused about how the "pos" will correspond with the other functions. I know after finishing the code, the function "eval_infix" should be able to call the related functions and get the output, but I don't really understand it clearly
 
  • #4
Hey FallArk! ;)

Suppose we want to evalute [1,"+",2,"+",3].
Then after calling eval_sum_infix, we will have evaluated "1+2", leaving "+3".
We can call eval_sum_infix again, but then we should continue at pos=3...
 
  • #5
I like Serena said:
Hey FallArk! ;)

Suppose we want to evalute [1,"+",2,"+",3].
Then after calling eval_sum_infix, we will have evaluated "1+2", leaving "+3".
We can call eval_sum_infix again, but then we should continue at pos=3...

so using recursion?
 
  • #6
Or maybe a while loop? the idea is that once it hit ";" the program stops.
 
  • #7
FallArk said:
so using recursion?

FallArk said:
Or maybe a while loop? the idea is that once it hit ";" the program stops.

It seems you already have all the answers! :)
 
  • #8
I like Serena said:
It seems you already have all the answers! :)

thanks! i will try them out and share it
 
  • #9
I like Serena said:
It seems you already have all the answers! :)

I have one more question though, if the ultimate goal is to call the function "eval_infix" with some parameters like "('2 * 3')", how can i make it so that the functions within will work together?
 
  • #10
FallArk said:
I have one more question though, if the ultimate goal is to call the function "eval_infix" with some parameters like "('2 * 3')", how can i make it so that the functions within will work together?

Well, from the comments, I'd say that we expect an input like "1 + 2 * 3 * 4 + ( 5 + 6 + 7 ) * ( 8 + 9 )".
First step splits it on spaces into a list, and appends [";"].
Then the result is evaluated as a sum of sub expressions.
That means we should work from left to right, evaluate sub expressions, and sum the results together.
When we run into a "(" token, we should evaluate the following part as a parenthesized expression, containing another sum-expression.
And if we run into a "*" token, we should evaluate the corresponding part as a series of multiplications.
 
  • #11
My code so far:
Code:
def eval_infix_sum(expr,pos):
    while expr[pos] != ';':
        if expr[pos+1] == '+' :
            ans = int(expr[pos]) + int(expr[pos+2])
        elif expr[pos+1] == '-' :
            ans = int(expr[pos]) - int(expr[pos+2])
        pos = pos + 1
    return ans,pos
def eval_infix_product(expr,pos):
    while expr[pos] != ';':
        if expr[pos+1] == '*' :
            ans = int(expr[pos]) * int(expr[pos+2])
        elif expr[pos+1] == '/' :
            ans = int(expr[pos]) / int(expr[pos+2])
        pos = pos + 1
    return ans,pos
Inputs like :
Code:
["1","+","2","-3",";"],0
works out just fine. Thanks for the comments, so inside the "eval_infix_factor" function, I should do something so that the "(" token can be dealt with then?
 
  • #12
FallArk said:
My code so far:
Code:
def eval_infix_sum(expr,pos):
    while expr[pos] != ';':
        if expr[pos+1] == '+' :
            ans = int(expr[pos]) + int(expr[pos+2])
        elif expr[pos+1] == '-' :
            ans = int(expr[pos]) - int(expr[pos+2])
        pos = pos + 1
    return ans,pos
def eval_infix_product(expr,pos):
    while expr[pos] != ';':
        if expr[pos+1] == '*' :
            ans = int(expr[pos]) * int(expr[pos+2])
        elif expr[pos+1] == '/' :
            ans = int(expr[pos]) / int(expr[pos+2])
        pos = pos + 1
    return ans,pos
Inputs like :
Code:
["1","+","2","-3",";"],0
works out just fine. Thanks for the comments, so inside the "eval_infix_factor" function, I should do something so that the "(" token can be dealt with then?

What we have is sum-expressions that consist of multiplicative-expressions that consist of either constants or parenthesized expressions.
In pseudo code it's something like this. ("rhs" is short for right hand side.)

Code:
def sum_expr
    result = mul_expr
    while next token == "+"
        rhs = mul_expr
        result += rhs
    return result

def mul_expr
    result = factor_expr
    while next token == "*"
        rhs =factor_expr
        result *= rhs
    return result

def factor_expr
    if next token == "("
        result = sum_expr
        skip following ")"
    else
        result = constant
    return result
All the parameters, and tracking of the position still have to be added.
 
  • #13
duh, I just realized that if input like " '2 + 3' " is entered, the function "eval_infix" will split it up into a list with semicolon and then call function "eval_infix_list" which will call "eval_infix_sum". :D
I will talk to my instructor today and also ask him about it again. Thank you!
 
  • #14
I like Serena said:
What we have is sum-expressions that consist of multiplicative-expressions that consist of either constants or parenthesized expressions.
In pseudo code it's something like this. ("rhs" is short for right hand side.)

Code:
def sum_expr
    result = mul_expr
    while next token == "+"
        rhs = mul_expr
        result += rhs
    return result

def mul_expr
    result = parentheses_expr
    while next token == "*"
        rhs = parentheses_expr
        result *= rhs
    return result

def parentheses_expr
    if next token == "("
        result = sum_expr
        skip following ")"
    else
        result = constant
    return result
All the parameters, and tracking of the position still have to be added.

I'm assuming that "eval_infix_factor" is the one that will be dealing with parentheses. My thinking(if that is indeed the case):
1. this function should detect a "(" then directly call "eval_infix_sum" since multiplication is higher order(not sure if this is the correct word) than addition
2. but how can it just know where the ")" will show up? Can I assume it will be three positions after the "(" ? How can I achieve that?

I'm still working on making the "sum" function and "product" function call each other when needed
 
  • #15
FallArk said:
I'm assuming that "eval_infix_factor" is the one that will be dealing with parentheses. My thinking(if that is indeed the case):
1. this function should detect a "(" then directly call "eval_infix_sum" since multiplication is higher order(not sure if this is the correct word) than addition
2. but how can it just know where the ")" will show up? Can I assume it will be three positions after the "(" ? How can I achieve that?

I'm still working on making the "sum" function and "product" function call each other when needed

Yes. I've edited my previous post to use factor_expr instead of parentheses_expr to avoid confusion.
And indeed multiplication has higher precedence, priority, or order than summation.

There's no need to know when the ')' will show up.
The enclosed sum expression will end when there's no "+" after the last factor (because there will be a ")").
It means that a ")" has to follow, or we have an error in the expression.
When the top-level sum expression ends, again there will be no "+" after the last factor (because there will be a ";").
If there's no ";", we have an error in the expression and could report that.

For the record, we never have to look further ahead than 1 token.
 
  • #16
I like Serena said:
Yes. I've edited my previous post to use factor_expr instead of parentheses_expr to avoid confusion.
And indeed multiplication has higher precedence, priority, or order than summation.

There's no need to know when the ')' will show up.
The enclosed sum expression will end when there's no "+" after the last factor (because there will be a ")").
It means that a ")" has to follow, or we have an error in the expression.
When the top-level sum expression ends, again there will be no "+" after the last factor (because there will be a ";").
If there's no ";", we have an error in the expression and could report that.

For the record, we never have to look further ahead than 1 token.

In the code template given, function "eval_infix_list" calls "eval_infix_sum" instead of "eval_infix_factor", how can the program check for parentheses then?
 
  • #17
FallArk said:
In the code template given, function "eval_infix_list" calls "eval_infix_sum" instead of "eval_infix_factor", how can the program check for parentheses then?

3 levels deep.
Note that [M]eval_infix_sum[/M] expects zero or more additions.
When we start evaluating the sum, the first thing we expect is a multiplication (of zero or more multiplications).
Within the multiplication, the first thing we expect is a factor.
When we check for the factor, we finally recognize the "(".
And when we get to the corresponding ")" there could be a "+" after it, or not.
 
  • #18
I like Serena said:
3 levels deep.
Note that [M]eval_infix_sum[/M] expects zero or more additions.
When we start evaluating the sum, the first thing we expect is a multiplication (of zero or more multiplications).
Within the multiplication, the first thing we expect is a factor.
When we check for the factor, we finally recognize the "(".
And when we get to the corresponding ")" there could be a "+" after it, or not.

So when running the program, "eval_infix_sum" will be called first, then it will call for product and product will cal factor, while not finding a multiplication, factor will check for a parentheses and call sum again.
 
  • #19
FallArk said:
So when running the program, "eval_infix_sum" will be called first, then it will call for product and product will cal factor, while not finding a multiplication, factor will check for a parentheses and call sum again.

Yes, except that eval_infix_factor does not have to check for a multiplication.
That will implicitly happen from its call to eval_infix_sum.
 
  • #20
I like Serena said:
Yes, except that eval_infix_factor does not have to check for a multiplication.
That will implicitly happen from its call to eval_infix_sum.

The function "eval_infix_factor" returns "int(expr[pos]), pos + 1" which I think only happens when there is no parentheses, right?
 
  • #21
FallArk said:
The function "eval_infix_factor" returns "int(expr[pos]), pos + 1" which I think only happens when there is no parentheses, right?

Correct. (Nod)
 
  • #22
I like Serena said:
Correct. (Nod)

Let's say the input is "2 + 3 - 1", the program should run sum first, and inside sum, it checks for product, then inside product, it will call factor to see if there is parentheses. since in this case, there is no parentheses, isn't the program will just output 2 and update pos from 0 to 1? I'm confused, how can it still call sum if it just ends
 
  • #23
FallArk said:
Let's say the input is "2 + 3 - 1", the program should run sum first, and inside sum, it checks for product, then inside product, it will call factor to see if there is parentheses. since in this case, there is no parentheses, isn't the program will just output 2 and update pos from 0 to 1? I'm confused, how can it still call sum if it just ends

Factor will return 2 instead of outputting 2. And it will return a pos of 1 as well. It will return to product.
Then product will see there is no "*" and return 2 as well, and pass pos=1 on.
Then sum will see there is a "+", increment pos, and start the next recursive call to product.
 
  • #24
I like Serena said:
Factor will return 2 instead of outputting 2. And it will return a pos of 1 as well. It will return to product.
Then product will see there is no "*" and return 2 as well, and pass pos=1 on.
Then sum will see there is a "+", increment pos, and start the next recursive call to product.

I thought a return statement will end a function call, how can it call product again?
 
  • #25
FallArk said:
I thought a return statement will end a function call, how can it call product again?

A return statement ends indeed a function call.
It doesn't call product, it returns to product to the point where the call came from.
 
  • #26
I like Serena said:
A return statement ends indeed a function call.
It doesn't call product, it returns to product to the point where the call came from.

I have this for factor:
Code:
def eval_infix_factor(expr,pos):
    if expr[pos] == '(':
        ans = eval_infix_sum(expr,pos)
    else:
        return int(expr[pos]),pos+1
Is it correct?
 
  • #27
FallArk said:
I have this for factor:
Code:
def eval_infix_factor(expr,pos):
    if expr[pos] == '(':
        ans = eval_infix_sum(expr,pos)
    else:
        return int(expr[pos]),pos+1
Is it correct?

The idea is correct, but eval_infix_sum returns both "ans" and "pos", and you need the pos that it returns.
And we return from the function in the else-part... but not in the if-part and we should.
 
  • #28
I like Serena said:
And we return from the function in the else-part... but not in the if-part and we should.
I didn't really understand this sentence:confused:
 
  • #29
FallArk said:
I didn't really understand this sentence:confused:

If we have a parenthesized expression the function doesn't return the answer (and instead returns an empty object).
If we have a constant expression, the function does return the answer.
We should return an answer in the case of a parenthesized expression as well.
 
  • #30
Just as an interesting reference, an extraction/simplification of an expression in the C/C++ programming language gives us the following syntax. See for instance here.
The standardized format of this syntax is called Backus-Naur Form.
Code:
<additive-expression> ::= <multiplicative-expression>
                        | <additive-expression> + <multiplicative-expression>
                        | <additive-expression> - <multiplicative-expression>

<multiplicative-expression> ::= <unary-expression>
                              | <multiplicative-expression> * <unary-expression>
                              | <multiplicative-expression> / <unary-expression>
                              | <multiplicative-expression> % <unary-expression>

<unary-expression> ::= <postfix-expression>
                     | <unary-operator> <unary-expression>

<postfix-expression> ::= <primary-expression>
                       | <postfix-expression> [ <additive-expression> ]

<primary-expression> ::= <identifier>
                       | <constant>
                       | <string>
                       | ( <additive-expression> )

So if we feel up to it, we could extend our expressions with a unary minus/plus, variables, strings, and arrays! :D

For the record, these also show the "official" names: additive-expression, multiplicative-expression, and primary-expression, for what we've been doing.
 
  • #31
Working solution:
Code:
def eval_infix_sum(expr,pos):
    ans, pos = eval_infix_product(expr,pos)
    while expr[pos] == '+' or expr[pos] == '-':
        if expr[pos] == '+':
            rhs,pos = eval_infix_product(expr,pos + 1)
            ans = ans + rhs
        elif expr[pos] == '-':
            rhs,pos = eval_infix_product(expr,pos + 1)
            ans = ans - rhs
    return ans,pos
def eval_infix_product(expr,pos):
    ans,pos = eval_infix_factor(expr,pos)
    while expr[pos] == '*' or expr[pos] == '/' or expr[pos] == '%':
        if expr[pos] == '*':
            rhs,pos = eval_infix_factor(expr,pos + 1)
            ans = ans * rhs
        elif expr[pos] == '/':
            rhs,pos = eval_infix_factor(expr,pos + 1)
            ans = ans / rhs
        elif expr[pos] == '%':
            rhs,pos = eval_infix_factor(expr,pos + 1)
            ans = ans % rhs
    return ans,pos
def eval_infix_factor(expr,pos):
    if expr[pos] == '(':
        ans,pos = eval_infix_sum(expr,pos+1)
        return ans,pos+1
    else:
        return int(expr[pos]),pos+1
def eval_infix_list(expr):
    ans,discard = eval_infix_sum(expr,0)
    return ans
def eval_infix(expr):
    return eval_infix_list(expr.split() + [ ";"])
Working on making it support minus(es?):p
 
  • #32
Looks good! (Yes)
 

FAQ: Help with Python: Implementing Algorithm

What is an algorithm?

An algorithm is a set of step-by-step instructions or rules used to solve a problem or perform a task. In computer science, algorithms are commonly used to process and manipulate data.

How do I implement an algorithm in Python?

To implement an algorithm in Python, you need to first understand the logic behind the algorithm. Then, you can use the built-in data structures and functions in Python to write the code for the algorithm. It is important to break down the algorithm into smaller, manageable steps and test each step as you go.

Can I use any algorithm in Python?

Yes, Python is a versatile programming language that can be used to implement a wide range of algorithms. However, some algorithms may be more efficient or easier to implement in other programming languages.

Are there any resources for learning how to implement algorithms in Python?

Yes, there are many online tutorials, courses, and books available for learning how to implement algorithms in Python. You can also refer to the official Python documentation for guidance on specific data structures and functions.

How can I test my implementation of an algorithm in Python?

You can test your implementation of an algorithm in Python by using different inputs and comparing the expected output to the actual output. You can also use debugging tools to step through your code and identify any errors or inefficiencies.

Similar threads

Replies
7
Views
4K
Replies
2
Views
2K
Replies
2
Views
2K
Replies
6
Views
3K
Replies
4
Views
5K
Back
Top