50017. Expression

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

Problem Description

Write a program to recognize an "expression". A string s is a valid expressesion if it satisfy any of the following condition.

  1. A single digit (0 to 9) is an expression.
  2. If S is an expression, then -S is also an expression.
  3. If S and T are both expressions, then (S+T) and (S-T) are both expressions.
  4. If S and T are both expressions, then (S*T) and (S/T) are both expressions.

BNF

<digit> → 0|1|2|3|4|5|6|7|8|9
<expression> →  <digit>
<expression> →  - <expression>
<expression> → (<expression> + <expression>) |
               (<expression> - <expression>) |
               (<expression> * <expression>) |
               (<expression> / <expression>)

For example, 4 is an expression because of condition 1. (4+3) is also an expression because both 4 and 3 are expressions. Similarly ((3*4)+5) is also an expression. However, (-9), (3+4+5) and 2+4 are not valid.

You need to implement the following function. It returns the value of the expression if the given string is an expression, -2147483648 otherwise. All arithmetic operations are for integers.

1
int expression(char *string);

Subtasks

  • 10pt. You only need to recognize the first condition, and the expression is always correct.
  • 15pt. You only need to recognize the first two conditions, and the expression is always correct.
  • 35pt. You only need to recognize the first three conditions, and the expression is always correct.
  • 30pt. You need to recongnize the all four conditions, and the expression is always correct.
  • 10pt. You need to recongnize the all four conditions. However, the expresion may be incorrect, or the "divide by zero" error may occur. In both cases the function should return -2147483648.

Hint

  • One can solve this problem recursively. However, we need to go through the string and remember where we are. For example, if we see a '(' we know we can recursively find an expression after it and know its value. The problem is, we need to know where to resume after that. For example, when we see ((3*4)+5) we can recursively find the expression (3*4) after the first (, but we must know that we need to resume at +. That is, both the value and where we are within the expression must be properly handled during the recursion. You may find the following prototype useful. The return value is the result of the evaluation, and *length will tell you the length of the expression found.
    int expressionEval(char *string, int *length);
  • You can convert a char '4' into integer by subtracting '0' from it.

Source Codes

main.c

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
#include <string.h>
#include "expression.h"
 
char buf[1<<20];
int main() {
    while (scanf("%s", buf) == 1) {
        int ret = expression(buf);
        printf("%d\n", ret);
    }
    return 0;
}

expression.h

1
int expression(char *string);

expression.c

1
2
3
4
5
6
#include "expression.h"
 
int expression(char *string){
    // Fill your code in here.
 
}

Sample Input

0
-5
--5
(4+3)
((3*4)+5)
((7/3)*((3/7)+1))
((3+3)/(2-2))
(-9)
-(3+5)(3+5)

Sample Output

0
-5
5
7
17
2
-2147483648
-2147483648
-2147483648

Discussion