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
eval.c
#include "eval.h"
int eval( int exp []) {
}
|
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$
Sample Output 0
Sample Input 1
$1 + 2 \ast -3 + 4 / 5 \ast 6 = -5$
Sample Output 2
Sample Input 3
$1 + 4 \ast 3 / 2 = 7$
Sample Output 3
Sample Input 4
$1 ? 3$
Sample Output 4
Sample Input 4
$1 / 0$
Sample Output 4