40 लाइनों में पार्सिंग सूत्र

कभी-कभी एक छोटे से काम (जैसे साक्षात्कार में दिए गए) को लेना दिलचस्प है और इसके लिए एक असामान्य समाधान ढूंढना है।
इस बार यह यैंडेक्स से ऐसा काम बन गया। पोस्ट और टिप्पणियों में, कई समाधान विकल्प प्रस्तावित किए गए थे, इस विषय का विषय एक कार्यात्मक शैली में एक लघु समाधान की खोज होगा।

सबसे पहले, डेटा संरचनाओं का चयन करें - यह रिवर्स पोलिश प्रविष्टि में एक पंक्ति होगी। हम स्वयं स्ट्रिंग उत्पन्न नहीं करेंगे, लेकिन हम मूल अभिव्यक्ति को संसाधित करने के दौरान तुरंत परिणाम की गणना करेंगे। हम दो स्टैक का उपयोग करेंगे - मूल्यों के लिए और संचालन के लिए। एक सहयोगी सरणी भी होगी जिसमें ऑपरेशन और संबंधित फ़ंक्शन शामिल हैं।
प्रत्येक ऑपरेशन में प्राथमिकता है। कोष्ठक खोलते समय, हम कोष्ठक में संचालन की प्राथमिकता बढ़ाएंगे, और जब बंद करेंगे, तो हम कम हो जाएंगे। ब्रैकेट खुद को स्टैक पर नहीं धकेल दिया जाता है। इसके अलावा, मानक प्रसंस्करण एल्गोरिथ्म और रिवर्स पोलिश अंकन में अभिव्यक्ति की गणना।

परिणामी कोड है:

#include <iostream> #include <map> #include <stack> #include <functional> #include <utility> #include <stdlib.h> using namespace std; int main(int argc, char** argv) { stack<double> s; stack< pair<int, char> > ops; auto p = [&s, &ops] (function<double (double, double)>& f) {double r=s.top();s.pop();r=f(s.top(),r);s.pop();s.push(r);ops.pop();}; map< char, pair< int, function<double (double, double)> > > m = {{'+', {1, [](double a, double b){return a+b;}}},{'-', {1, [](double a, double b){return ab;}}}, {'*', {2, [](double a, double b){return a*b;}}},{'/', {2, [](double a, double b){return a/b;}}}}; const int order = 2; int level = 0; for (char* sp = argv[1];; ++sp) { while (*sp == '(') {level += order; ++sp;} s.push(strtod(sp, &sp)); while (*sp == ')') {level -= order; ++sp;} if (!*sp) {while(!ops.empty()) p(m[ops.top().second].second); break;} const int op = m[*sp].first + level; while (!ops.empty() && ops.top().first >= op) p(m[ops.top().second].second); ops.push(make_pair(op, *sp)); } cout << s.top() << endl; return 0; } 

चल रहा है:

 ./calc "15/(7-(1+1))*3-(2+(1+1))" 5