学步园

无聊题，中缀表达式。一口气写了290行，就如炎炎烈日下当头一兜凉水般的爽快。

#include <iostream><br /> #include <string><br /> #include <vector><br /> #include <stack><br /> #include <cctype><br /> using namespace std;</p> <p>string str;<br /> int cs = 1;</p> <p>int lev ( char c )<br /> {<br /> if ( c == '+' || c == '-' )<br /> return 1;<br /> if ( c == '*' )<br /> return 2;<br /> if ( c == '(' || c == '@' )<br /> return 0;<br /> return -1;<br /> }</p> <p>void print ( const vector <int> &v )<br /> {<br /> int i;<br /> for ( i = 0; i < v.size (); i ++ )<br /> {<br /> if ( v[i] == -1000 )<br /> printf ( "x" );<br /> else if ( v[i] >= 0 )<br /> printf ( "%d", v[i] );<br /> else<br /> printf ( "%c", v[i] + 500 );<br /> }<br /> printf ( "/n" );<br /> }</p> <p>void proc ()<br /> {<br /> int i = str.find_first_of ( '=' );<br /> string left = str.substr ( 0, i );<br /> string right = str.substr ( i + 1, str.size () );<br /> left += '@', right += '@';</p> <p> stack <int> is;<br /> stack <int> xs;<br /> stack <char> cs;<br /> vector <int> iv;<br /> int sum = 0;<br /> cs.push ( '@' );</p> <p> for ( i = 0; i < left.size (); i ++ )<br /> {<br /> if ( left[i] == 'x' )<br /> {<br /> iv.push_back ( -1000 );<br /> }<br /> else if ( isdigit ( left[i] ) )<br /> {<br /> sum = sum * 10 + left[i] - '0';<br /> if ( !isdigit ( left[i + 1] ) )<br /> {<br /> iv.push_back ( sum );<br /> sum = 0;<br /> }<br /> }<br /> else if ( left[i] != '@' )<br /> {<br /> if ( left[i] == '(' )<br /> {<br /> cs.push ( '(' );<br /> }<br /> else if ( left[i] == ')' )<br /> {<br /> while ( cs.top () != '(' )<br /> {<br /> iv.push_back ( cs.top () - 500 );<br /> cs.pop ();<br /> }<br /> cs.pop ();<br /> }<br /> else<br /> {<br /> char ch = left[i];<br /> if ( lev ( ch ) > lev ( cs.top () ) )<br /> cs.push ( ch );<br /> else<br /> {<br /> while ( lev ( cs.top () ) >= lev ( ch ) )<br /> {<br /> iv.push_back ( cs.top () - 500 );<br /> cs.pop ();<br /> }<br /> cs.push ( ch );<br /> }<br /> }<br /> }<br /> else<br /> {<br /> while ( cs.top () != '@' )<br /> {<br /> iv.push_back ( cs.top () - 500 );<br /> cs.pop ();<br /> }<br /> }<br /> }</p> <p> int la = 0, lb = 0; // ax = b<br /> for ( i = 0; i < iv.size (); i ++ )<br /> {<br /> if ( iv[i] >= 0 )<br /> {<br /> is.push ( iv[i] );<br /> xs.push ( 0 );<br /> }<br /> else if ( iv[i] == -1000 )<br /> {<br /> is.push ( 0 );<br /> xs.push ( 1 );<br /> }<br /> else<br /> {<br /> char ch = iv[i] + 500;<br /> int a1 = xs.top ();<br /> xs.pop ();<br /> int a2 = xs.top ();<br /> xs.pop ();<br /> int b1 = is.top ();<br /> is.pop ();<br /> int b2 = is.top ();<br /> is.pop ();<br /> if ( ch == '+' )<br /> {<br /> xs.push ( a1 + a2 );<br /> is.push ( b1 + b2 );<br /> }<br /> if ( ch == '-' )<br /> {<br /> xs.push ( a1 - a2 );<br /> is.push ( b1 - b2 );<br /> }<br /> if ( ch == '*' )<br /> {<br /> if ( a1 == 0 && a2 == 0 )<br /> xs.push ( 0 );<br /> if ( a1 == 0 && a2 != 0 )<br /> xs.push ( a2 * b1 );<br /> if ( a2 == 0 && a1 != 0 )<br /> xs.push ( a1 * b2 );<br /> is.push ( b1 * b2 );<br /> }<br /> }<br /> }<br /> la = xs.top ();<br /> lb = is.top ();<br /> xs.pop ();<br /> is.pop ();<br /> //printf ( "%d %d/n", a, b );<br /> //print ( iv );<br /> iv.clear ();</p> <p> for ( i = 0; i < right.size (); i ++ )<br /> {<br /> if ( right[i] == 'x' )<br /> {<br /> iv.push_back ( -1000 );<br /> }<br /> else if ( isdigit ( right[i] ) )<br /> {<br /> sum = sum * 10 + right[i] - '0';<br /> if ( !isdigit ( right[i + 1] ) )<br /> {<br /> iv.push_back ( sum );<br /> sum = 0;<br /> }<br /> }<br /> else if ( right[i] != '@' )<br /> {<br /> if ( right[i] == '(' )<br /> {<br /> cs.push ( '(' );<br /> }<br /> else if ( right[i] == ')' )<br /> {<br /> while ( cs.top () != '(' )<br /> {<br /> iv.push_back ( cs.top () - 500 );<br /> cs.pop ();<br /> }<br /> cs.pop ();<br /> }<br /> else<br /> {<br /> char ch = right[i];<br /> if ( lev ( ch ) > lev ( cs.top () ) )<br /> cs.push ( ch );<br /> else<br /> {<br /> while ( lev ( cs.top () ) >= lev ( ch ) )<br /> {<br /> iv.push_back ( cs.top () - 500 );<br /> cs.pop ();<br /> }<br /> cs.push ( ch );<br /> }<br /> }<br /> }<br /> else<br /> {<br /> while ( cs.top () != '@' )<br /> {<br /> iv.push_back ( cs.top () - 500 );<br /> cs.pop ();<br /> }<br /> }<br /> }</p> <p> int ra = 0, rb = 0; // ax = b<br /> for ( i = 0; i < iv.size (); i ++ )<br /> {<br /> if ( iv[i] >= 0 )<br /> {<br /> is.push ( iv[i] );<br /> xs.push ( 0 );<br /> }<br /> else if ( iv[i] == -1000 )<br /> {<br /> is.push ( 0 );<br /> xs.push ( 1 );<br /> }<br /> else<br /> {<br /> char ch = iv[i] + 500;<br /> int a1 = xs.top ();<br /> xs.pop ();<br /> int a2 = xs.top ();<br /> xs.pop ();<br /> int b1 = is.top ();<br /> is.pop ();<br /> int b2 = is.top ();<br /> is.pop ();<br /> if ( ch == '+' )<br /> {<br /> xs.push ( a1 + a2 );<br /> is.push ( b1 + b2 );<br /> }<br /> if ( ch == '-' )<br /> {<br /> xs.push ( a1 - a2 );<br /> is.push ( b1 - b2 );<br /> }<br /> if ( ch == '*' )<br /> {<br /> if ( a1 == 0 && a2 == 0 )<br /> xs.push ( 0 );<br /> if ( a1 == 0 && a2 != 0 )<br /> xs.push ( a2 * b1 );<br /> if ( a2 == 0 && a1 != 0 )<br /> xs.push ( a1 * b2 );<br /> is.push ( b1 * b2 );<br /> }<br /> }<br /> }<br /> ra = xs.top ();<br /> rb = is.top ();<br /> xs.pop ();<br /> is.pop ();</p> <p> //printf ( "%d %d/n", la, lb );<br /> //printf ( "%d %d/n", ra, rb );<br /> int a = la - ra, b = rb - lb;<br /> if ( a == 0 && b == 0 )<br /> printf ( "Infinitely many solutions./n" );<br /> else if ( a == 0 && b != 0 )<br /> printf ( "No solution./n" );<br /> else<br /> printf ( "x = %f/n", double ( b ) / double ( a ) );<br /> }</p> <p>int main ()<br /> {<br /> //freopen ( "in.txt", "r", stdin );<br /> while ( getline ( cin, str ) )<br /> {<br /> printf ( "Equation #%d/n", cs ++ );<br /> proc ();<br /> printf ( "/n" );<br /> }<br /> return 0;<br /> }