/* Propositional logic translator, infix-to-postfix Sten Morten Andersen, 2003 Grammar: formula ::= expression { ('>' | '=') formula } expression ::= term { 'v' term } term ::= factor { '&' factor } factor ::= 'a' | 'b' | 'c' | .. | 'z' | '-' formula | '(' formula ')' */ char ch; char stack[100]; int top; void formula(); void error(char *s) { printf("%s. Seen %c\n", s, ch); exit(1); } void get_char() { do ch = getchar(); while ( ch <= ' ' ); } void factor() { char c = ch; if ( ch == '0' || ch == '1' ) ch = 'L'; switch( ch ) { case 'L': stack[ top++ ] = c; get_char(); break; case '-': get_char(); formula(); stack[ top++ ] = 'N'; break; case '(': get_char(); formula(); if ( ch != ')' ) error("Missing )"); get_char(); break; default: error("Expected 0, 1 or (formula)"); } } void term() { factor(); while ( ch == '&' ) { get_char(); factor(); stack[ top++ ] = 'K'; } } void expression() { term(); while ( ch == 'v' ) { get_char(); term(); stack[ top++ ] = 'A'; } } void formula() { char c; expression(); while ( ch == '>' || ch == '=') { c = ch; get_char(); formula(); if ( c == '=' ) stack[ top++ ] = 'E'; if ( c == '>' ) stack[ top++ ] = 'C'; } } int eval() { int i, t = -1; int s[100]; for ( i = 0; i < top; i++ ) { if ( stack[ i ] == '0' || stack[ i ] == '1' ) { t++; s[ t ] = stack[ i ]-'0'; } else { t--; switch ( stack[ i ] ) { case 'A': s[ t ] = s[ t ] || s[ t+1 ]; break; case 'C': s[ t ] = s[ t ] <= s[ t+1 ]; break; case 'E': s[ t ] = s[ t ] == s[ t+1 ]; break; case 'K': s[ t ] = s[ t ] && s[ t+1 ]; break; case 'N': t++; s[ t ] = ! s[ t ]; break; } } } return s[ t ]; } int main() { top = 0; get_char(); formula(); if ( ch != '.') error ("Expected ."); int e = eval(); printf("%d",e); return 0; }