Solving An Equation in an Array

Question

Hello hello,

Im trying to figure out how i can solve an equation that has been stored in an array. I need some guidance on how to conquer such problem. here is my conditions

• i have an array int X[30];
• and in there i have stored my desired equation: 5+6*20/4
• as well, i couldnt store the operants (+ / - * ) so i used different identifiers for them like ( -1 -2 -3 -4 ) because there should not be a negative value in the equation.

any help would be greatly appreciated

thanks

Answer 1

That sounds like a less than ideal way to represent an equation. Do you need to honour correct mathematical operator precedence? In other words, does the 6*20/4 take precedence over the 5+6?

The robust way to solve it is to use tools like flex and bison to create code from a grammar for the language. But if this is a small homework assignment rather than production code then you can probably hack something together by scanning left to right... skip +- operations and evaluate */ operations in place (make sure you shift down the rest of the array elements). After you've reduced out all the */ operations then you can evaluate the +- operations.

Step 0: 5+6*20/4
Step 1: 5+120/4
Step 2: 5+30
Step 3: 35

Answer 2

http://stackoverflow.com/questions/28256/equation-expression-parser-with-precedence

Answer 3

As you've discovered, an int array is a poor abstraction for an equation.

C++ is an object-oriented language. Start thinking in terms of objects and try to abstract some of the characteristics of equations.

You want something more like this.

Answer 4

You can store the values followed by an operator in order. Since a value will be always followed by an operator you don't have to worry about figuring with negatives, or mixing them up.

For the operators (+ / - *), you can directly store it as an ASCII character since characters are one byte integers. The operators then would translate to (+ / - *) -> (43 47 45 42) For example, your equation above would look like:

• array[0] -> 5
• array[1] -> 43
• array[2] -> 6
• array[3] -> 42
• array[4] -> 20
• array[5] -> 47
• array[6] -> 4

Optional: You can add a special character to signify the end of your equation

• array[7] -> your choice

If space or performance is a worry you can complicate things a lot more but I think its okay in this case.

Answer 5

Normally, you have to define the priority of each operation and process each of them one by one.

First your expression is:        '`[ 5,-1, 6,-4,20,-2, 4]`'
Do all '/' first:                '`[ 5,-1, 6,-4, 5,-1, 0]`' <- 20/ 4 =  5+0
Then, do all '*':                '`[ 5,-1,30,-1, 0,-1, 0]`' <-  6* 5 = 30+0
Then, do all '-':                '`[ 5,-1,30,-1, 0,-1, 0]`' <-  Nothing
Then, do all '+' (sum positive): '`[35,-1, 0,-1, 0,-1, 0]`' <-  5+30+0+0 = 35 + 0 + 0

ADDED: Here is the C code.

void ShowArray(int pX[], int pLength) {
    int i;
    for(i = 0; i < pLength; i++)
     printf("%3d ", pX[i]);
    printf("\n");
}
 
void ShiftArray(int pX[], int pIndex, int pSkip, int pLength) {
    int i;
    for(i = pIndex; i < (pLength - pSkip); i++)
     pX[i] = pX[i + pSkip];
 
    for(i = (pLength - pSkip); i < pLength; i++)
     pX[i] = 0;
}
 
int main(void) {
    const int OPERCOUNT =  4;
    const int PLUS      = -1;  // -1 Do last
    const int SUBT      = -2;
    const int MULT      = -3;
    const int DIV       = -4;  // -4 Do first
 
    int X[]    = {5, PLUS, 6, MULT, 20, DIV, 4};
    int XCount = 7;
 
    ShowArray(X, XCount);
 
    int i;
    for(i = OPERCOUNT; --i >= 0; ) {
     int OPER = -(i + 1);

     int j = 0;
     for(j = 0; j < XCount; j++) {
      int x = X[j];
      if (x == OPER) {
       if      (x == PLUS) X[j - 1] = X[j - 1] + X[j + 1];
       else if (x == SUBT) X[j - 1] = X[j - 1] - X[j + 1];
       else if (x == MULT) X[j - 1] = X[j - 1] * X[j + 1];
       else if (x == DIV ) X[j - 1] = X[j - 1] / X[j + 1];
       ShiftArray(X, j, 2, XCount);
      }
     }
 
     ShowArray(X, XCount);
    }
 
    int Sum = 0;
    int j;
    for(j = 0; j < XCount; j++) {
     int x = X[j];
     if (x > 0) Sum += x;
    }
    printf("Result: %d\n", Sum);
}

And here is the result:

  5  -1   6  -3  20  -4   4 
  5  -1   6  -3   5   0   0 
  5  -1  30   0   0   0   0 
  5  -1  30   0   0   0   0 
 35   0   0   0   0   0   0 
Result: 35

This should works.

Enjoy coding.

Answer 6

As others have noted, storing an equation into an array of integers is not the best thing in the world to do. Assuming this is not a homework assignment that requires you to use an array, I would suggest that you develop your own class that can handle equations more robustly.

As for your current array method, I would change it to a std::vector. And then I think I would implement something along these lines:

Go through the array until we find the operator with greatest precedence
Once we've found it, apply the operator and store the result in place of one of the numbers. Remove the operator and the unused number operated on from the vector
Keep going until the whole vector has had that particular operator applied
Go back to the beginning, but do this for the next-highest precedence operator

Answer 7

If this is to be done in C, then I'd suggest use prefix or postfix evaluation techniques. There are techniques to convert the given infix expression to prefix or postfix notation. You can read more on these notations and their conversions here

Using those, your equation (5+6*20/4) gets converted to the following prefix notation:

+ 5 * 6 / 20 4

Prefix = operator comes before any operands
Infix = operator is between operands
Postfix = operator is after both operands

When this is stored on two stacks, numbers and operations, here is what you get:

int nums[] = {4, 20, 6, 5);
char opers[] = {'/', '*', '+'}

Note the reversal of order.

You can now evaluate this using simple push pop technique along with precedence:

1. Pop an operator from operator stack
2. Pop two operands from operand stack and apply the operation to them
3. Push the result back on the stack

Continue the above until you are left with one result on the operand stack (and the operator stack is empty)

Trial run for the above:

Iteration 1:

Apply '/' to 4 and 20 giving 5, push it back on operand stack.

nums = {5, 6, 5};
opers = {'*', '+'};

--

Iteration 2:

Apply '*' to 5 and 6 giving 30, push it back on operand stack

nums = {30, 5};
opers = {'+'};

--

Iteration 3:

Apply '+' to 30 and 5 giving 35, push it back on operand stack

Now, operator stack is empty and operand stack has one value: 35, which is your answer.

Answer 8

Here's what I came up with quick. Not my cleanest code (almost didn't post it) but it respects the order of operations and can handle when the numbers go negative.

#include <stdio.h>

int main(int argc, char** argv){
    int e[] = {5,-1,6,-2,20,-4,4,-3,50,-1,100,-5};
    int l;

    printf("\n\n");
    int* cpi = e;
    while(*cpi != -5 ){
     if(*cpi == -1)
      printf(" +");
     else if(*cpi == -2)
      printf(" *");
     else if(*cpi == -3)
      printf(" -");
     else if(*cpi == -4)
      printf(" /");
     else
      printf(" %d",*cpi);
     *cpi = *cpi >= 0 ? *cpi + 1 : *cpi;
     cpi++;
    }
    printf("\n\n");

    int op1 = -2;
    int op2 = -4;


    int loop = 0;
    for(loop = 0 ; loop < 2 ; loop++){  
     cpi = e;
     while(*cpi != -5 ){
      if(*cpi == op1 || *cpi == op2){
       int* p1 = cpi-1;
       int* p2 = cpi+1;

       while(*p1 <= 0 && *p1 >= -5)
        p1--;

       while(*p2 <= 0 && *p2 >= -5)
        p2++;

       int v1 = *p1 > 0 ? *p1 - 1 : *p1 + 5;
       int v2 = *p2 > 0 ? *p2 - 1 : *p2 + 5;

       int r;

       if(*cpi == -2){
        r = v1 * v2;
        printf("%d * %d = %d\n",v1,v2,r);
       }
       else if(*cpi == -4){
        r = v1 / v2;
        printf("%d / %d = %d\n",v1,v2,r);
       }
       else if(*cpi == -1){
        r = v1 + v2;
        printf("%d + %d = %d\n",v1,v2,r);
       }
       else if(*cpi == -3){
        r = v1 - v2;
        printf("%d - %d = %d\n",v1,v2,r);
       }
       r = r >= 0 ? r + 1 : r - 5;

       *cpi = r;
       *p1 = 0;
       *p2 = 0;
      }
      cpi++;
     }
     op1 = -1;
     op2 = -3;
    }


    cpi = e;
    while(*cpi <= 0 && *cpi >= -5){
     cpi++;
    }
    int r = *cpi;
    r = r > 0 ? r - 1 : r + 5;
    printf("Result: %d\n",r);

    return 0;
}

Output:

5 + 6 * 20 / 4 - 50 + 100

6 * 20 = 120

120 / 4 = 30

5 + 30 = 35

35 - 50 = -15

-15 + 100 = 85

Result: 85

Answer 9

Thank you everyone for your intake and help.