50006. Expression

I'm a slow walker, but I never walk backwards.

Problem description

Write a program to process an expression. We will use an array (e.g. exp) to store the information about an expression. An expression consists of operators, including $+$, $-$, $\ast$ and $/$, and operands, like, $1$, $2$, and $-3$.

The first element $\text{exp}\lbrack 0]$ will be the sum of the number of operands and operators. For example, an expression $1 + 2 \ast -3 + 4 / 5 \ast 6$ has 5 operators and 6 operands, then $\text{exp}\lbrack 0]$ will be 11. Note that $\text{exp}\lbrack 0]$ is always an positive odd number (including 1) since the number of operand is always one greater than the number of the operators. Note that 3 is also a valid expression, with $\text{exp}\lbrack 0]$ equals to 1.

The rest of the array stores the operands and operators. All operators are integer operators, and all operands are integers. Here we use 1 for $+$, 2 for $-$, 3 for $\ast$ and 4 for $/$. For example, in the previous example, $\text{exp}\lbrack 1]$ will be 1, $\text{exp}\lbrack 2]$ will be 1, $\text{exp}\lbrack 3]$ will be 2, etc. Note that -3 is an operand so $\text{exp}\lbrack 5]$ will be -3.

Now given the array, please write function to evaluate the value of the expression the array represents. Note that you need to perform all $\ast$ and $/$ before $+$ and $-$. Also you need to perform these arithmetic functions from left to right. That is $1 + 4 \ast 3 / 2$ should be $(1 + ((4 \ast 3) / 2))$. You need to write the following function. The function has only a single parameter exp, and returns the value of the expression.

main.c

#include <stdio.h>
#include <string.h>
#include "eval.h"
 
int main() {
    int exp[1024];
    memset(exp, -1, sizeof(exp));
    scanf("%d", &exp[0]);
    for (int i = 1; i <= exp[0]; i++)
        scanf("%d", &exp[i]);
    int ret = eval(exp);
    printf("%d\n", ret);
    return 0;
}

eval.h

int eval(int exp[]);

eval.c

#include "eval.h"
 
int eval(int exp[]) {
    /* add your code */
}

Technical Specification and constraints

  • 10 pt. There are only $+$ in the expression, and the expression is always valid.
  • 20 pt. There are only $+$ and $-$ in the expression, and the expression is always valid.
  • 50 pt. There are $+$, $-$, $\ast$ and $/$ in the expression, and the expression is always valid. In addition the $*$ and $/$ will not be adjacent to each other. For example, both $3 \ast 2 \ast 1 + 1$ and $3 + 3 \ast 4 / 5$ are not allowed, but $1 \ast 2 + 6 + 3 \ast 4 - 5 / 6 - 7$ is allowed.
  • 10 pt. The expression may be invalid. The first case is that the code for operator may be invalid. In that case return -2147483646. The second case is divide-by-zero error. In that case return -2147483647. You must check the first case before the second case.
  • 10 pt. There are $+$, $-$, $\ast$ and $/$ in the expression, and the expression is always valid. There are no additional constraints so both $3 \ast 2 \ast 1 + 1$ and $3 + 3 \ast 4 / 5$ are allowed.

Sample Input 0

$1 + 7 - 3 = 5$

5
1 1 7 2 3

Sample Output 0

5

Sample Input 1

$1 + 2 \ast -3 + 4 / 5 \ast 6 = -5$

11
1 1 2 3 -3 1 4 4 5 3 6

Sample Output 2

-5

Sample Input 3

$1 + 4 \ast 3 / 2 = 7$

7
1 1 4 3 3 4 2

Sample Output 3

7

Sample Input 4

$1 ? 3$

3
1 0 3

Sample Output 4

-2147483646

Sample Input 4

$1 / 0$

3
1 4 0

Sample Output 4

-2147483647

Discussion