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 expression if it satisfies any of the following conditions.

  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 expression value 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 recognize all four conditions, and the expression is always correct.
  • 10pt. You need to recognize all four conditions. However, the expression 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 understand 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 +. We must adequately handle both the value and where we are within the expression during the recursion. You may find the following helpful prototype. The return value is the evaluation result, and *length will tell you the size of the expression found.
    int expressionEval(char *string, int *length);
  • You can convert a char '4' into an 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