{"id":1303,"date":"2024-12-14T09:00:00","date_gmt":"2024-12-14T01:00:00","guid":{"rendered":"https:\/\/seanxd.com\/?p=1303"},"modified":"2024-12-08T00:00:52","modified_gmt":"2024-12-07T16:00:52","slug":"zerojudge-f377","status":"publish","type":"post","link":"https:\/\/seanxd.com\/en\/zerojudge-f377\/","title":{"rendered":"ZeroJudge F377: Arithmetic Conversion"},"content":{"rendered":"\n\n\n

\u4e00\u822c\u6211\u5011\u5e38\u770b\u5230\u7684\u904b\u7b97\u5f0f\uff0c\u50cf\u662f a + b * c \u6216 a \/ b – c \u90fd\u662f\u4e2d\u5e8f\u904b\u7b97\u5f0f (Infix Notation)\uff0c\u53ef\u662f\u96fb\u8166\u4e0d\u61c2\u5f97\u5982\u4f55\u8655\u7406\u4e2d\u5e8f\u904b\u7b97\u5f0f\uff0c\u6240\u4ee5\u96fb\u8166\u6703\u5148\u628a\u4e2d\u5e8f\u904b\u7b97\u5f0f\u8f49\u6210\u5f8c\u5e8f\u904b\u7b97\u5f0f (Postfix Notation)\u6216\u524d\u5e8f\u904b\u7b97\u5f0f (Prefix Notation) \u518d\u8a08\u7b97\u3002\u73fe\u5728\u4f60\u7684\u4efb\u52d9\u662f\u5beb\u4e00\u500b\u7a0b\u5f0f\u6a21\u64ec\u4e2d\u5e8f\u904b\u7b97\u5f0f\u8f49\u63db\u6210\u5f8c\u5e8f\u904b\u7b97\u5f0f\u3002<\/p>\n\n\n\n

\u7bc4\u4f8b\u6e2c\u8cc7<\/h2>\n\n\n\n
\u7bc4\u4f8b\u8f38\u5165<\/th>\u7bc4\u4f8b\u8f38\u51fa<\/th><\/tr><\/thead>
EOF \u8f38\u5165
\u6bcf\u7b46\u6e2c\u8cc7\u4e00\u884c
\u6bcf\u4e00\u884c\u6703\u6709\u4e00\u500b\u4e2d\u5e8f\u904b\u7b97\u5f0f\uff0c\u6bcf\u500b\u904b\u7b97\u5b50\u53ca\u904b\u7b97\u5143\u90fd\u6703\u4ee5\u7a7a\u683c\u5206\u9694
\u904b\u7b97\u5143\u67096\u7a2e ‘+’\u3001’-‘\u3001’*’\u3001’\/’\u3001'(‘\u3001’)’
\u5206\u5225\u4ee3\u8868\u52a0\u6e1b\u4e58\u9664\u8207\u62ec\u865f
\u512a\u5148\u9806\u5e8f: \u62ec\u865f > \u4e58\u9664 > \u52a0\u6e1b
\u904b\u7b97\u5b50\u662f\u5c0f\u5beb\u7684\u82f1\u6587\u5b57\u6bcd<\/td>		\u8acb\u4f60\u8f38\u51fa\u9806\u5e8f\u7531\u5de6\u5230\u53f3\u8f49\u63db\u597d\u7684\u5f8c\u5e8f\u904b\u7b97\u5f0f
\u6bcf\u500b\u904b\u7b97\u5b50\u53ca\u904b\u7b97\u5143\u4ee5\u7a7a\u683c\u5206\u9694<\/td><\/tr>
a + b * c
a \/ b – c
a + b * ( c * ( d + e ) )<\/td>		a b c * +
a b \/ c –
a b c d e + * * +<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

\u89e3\u984c\u601d\u8def<\/h2>\n\n\n\n

\u4e00\u500b\u4e00\u500b\u5b57\u5143\u5224\u65b7\uff0c\u5982\u679c\u8b80\u5230\u5b57\u6bcd\u5c31\u76f4\u63a5\u5c07\u5176\u8f38\u51fa\u3002<\/p>\n\n\n\n

\u5ba3\u544a\u4e00\u500b stack\uff0c\u7528\u4f86\u5b58\u904b\u7b97\u5143\u3002\u7576\u8b80\u5230\u4e00\u500b\u904b\u7b97\u5143\u6642\u548c stack \u4e2d\u7684\u8cc7\u6599\u505a\u6bd4\u8f03\uff0c\u5982\u679c stack \u88e1\u9762\u6c92\u6709\u6771\u897f\u5c31\u5c07\u76ee\u524d\u7684\u904b\u7b97\u5143 push \u5230 stack \u4e2d\u3002\u53cd\u4e4b\uff0c\u8981\u5148\u5224\u65b7\u904b\u7b97\u5143\u662f\u5426\u662f\u53f3\u62ec\u865f\u300c)\u300d\uff0c\u5982\u679c\u662f\u53f3\u62ec\u865f\uff0c\u5c07 stack \u4e2d\u7684\u8cc7\u6599\u5f9e\u4e0a\u5230\u4e0b\u4f9d\u5e8f\u8f38\u51fa\uff0c\u76f4\u5230\u9047\u5230\u5de6\u62ec\u865f\u300c)\u300d\uff0c\u4e0d\u7528\u8f38\u51fa\u5de6\u62ec\u865f\u4f46\u662f\u8981 pop \u6389\u5b83\u3002\u5982\u679c\u662f\u5176\u4ed6\u7684\u904b\u7b97\u5143\u5247\u5224\u65b7\u76ee\u524d\u904b\u7b97\u5143\u7684\u512a\u5148\u5ea6\u662f\u5426 <= stack.top() \u7684\u512a\u5148\u5ea6\uff0c\u5982\u679c\u662f\u7684\u8a71\u5c31\u5c07 stack \u4e2d\u7684\u8cc7\u6599\u5f9e\u4e0a\u5230\u4e0b\u4f9d\u5e8f\u8f38\u51fa\uff0c\u4f46\u662f\u9047\u5230\u6bd4\u76ee\u524d\u9019\u500b\u904b\u7b97\u5143\u512a\u5148\u5ea6\u9084\u8981\u9ad8\u7684\u904b\u7b97\u5143\u5c31\u8981\u505c\u4e0b\uff0c\u6216\u662f\u9047\u5230\u5de6\u62ec\u865f\u4e5f\u8981\u505c\u4e0b\u3002\u5982\u679c\u4e0d\u662f\u53f3\u62ec\u865f\u6700\u5f8c\u90fd\u8981\u5c07\u904b\u7b97\u5143 push \u5230 stack \u4e2d\u3002\u6240\u6709\u904b\u7b97\u5b50\u548c\u904b\u7b97\u5143\u90fd\u5224\u65b7\u5b8c\u4e4b\u5f8c\u5c31\u5c07 stack \u4e2d\u7684\u300c\u6240\u6709\u8cc7\u6599\u300d\u5f9e\u4e0a\u5230\u4e0b\u8f38\u51fa\u3002<\/p>\n\n\n\n

\u7bc4\u4f8b\u7a0b\u5f0f\u78bc\uff0dZeroJudge f377: \u904b\u7b97\u5f0f\u8f49\u63db<\/a><\/h3>\n\n\n\n
#include <iostream>\n#include <stack>\n#include <unordered_map>\nusing namespace std;\n\nint main() {\n    cin.sync_with_stdio(0);\n    cin.tie(0);\n    unordered_map<char, int>MAP;\n    MAP['*'] = 1;\n    MAP['\/'] = 1;\n    MAP['('] = 2;\n    MAP[')'] = 2;\n    string str;\n    while (getline(cin, str)) {\n        stack<char> st;\n        for (int i = 0; i<str.length(); i++) {\n            const char ch = str[i];\n            if (ch == ' ') continue;\n            if (isalpha(ch)) cout << ch << " ";\n            else {\n                if (st.empty()) st.push(str[i]);\n                else {\n                    if (ch == ')') {\n                        while (!st.empty()) {\n                            if (st.top() == '(') {\n                                st.pop();\n                                break;\n                            }\n                            cout << st.top() << " ";\n                            st.pop();\n                        }\n                    }\n                    else {\n                        if (MAP[ch] <= MAP[st.top()]) {\n                            while (!st.empty() && MAP[ch] <= MAP[st.top()]) {\n                                if (st.top() == '(') {\n                                    break;\n                                }\n                                cout << st.top() << " ";\n                                st.pop();\n                            }\n                        }\n                        st.push(ch);\n                    }\n                }\n            }\n        }\n        while (!st.empty()) {\n            cout << st.top() << " ";\n            st.pop();\n        }\n        cout << "\\n";\n    }\n\n}\n\n\/\/ZeroJudge F377\n\/\/Dr. SeanXD<\/code><\/pre><\/div>\n","protected":false},"excerpt":{"rendered":"
\u4e00\u822c\u6211\u5011\u5e38\u770b\u5230\u7684\u904b\u7b97\u5f0f\uff0c\u50cf\u662f a + b * c \u6216 a \/ b – c \u90fd\u662f\u4e2d\u5e8f\u904b\u7b97\u5f0f (Inf […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","footnotes":""},"categories":[6],"tags":[14,54,8,11,9],"class_list":["post-1303","post","type-post","status-publish","format-standard","hentry","category-6","tag-map","tag-stack","tag-8","tag-11","tag-9"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/1303","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/comments?post=1303"}],"version-history":[{"count":3,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/1303\/revisions"}],"predecessor-version":[{"id":1306,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/1303\/revisions\/1306"}],"wp:attachment":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/media?parent=1303"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/categories?post=1303"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/tags?post=1303"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}