nyoj-257-中綴轉后綴

2019-11-06 06:39:49

字體：大中小

來源：轉載

供稿：網友

問題

題目：[nyoj-257]

思路

主要是需要一個操作符棧，對于操作數而言直接輸出就行。對于操作符棧，大致的規則很簡單，就是如果當前元素優先級高于棧頂優先級，棧頂出棧。直到當前元素的優先級高于棧頂或者是棧為空，入棧。最后。將棧中元素挨個出棧，附加到尾部即可。

整體思路不難，比較麻煩的是對于對于操作符的優先級。

主要是左右括號在棧外和棧內的優先級不同導致。同一級別的操作符，先入棧的優先級高。

對于同一級別的優先級，一定要遵循“同一優先級，從左到右計算” 比如，1-2+3，如果從右向左計算 1 - （2+3）=-4，主要是操作數入棧我們默認的都是正數。所以，這么做會丟失負號。必須嚴格按照從左到右的計算順序。

規則按照當前不同元素來進行劃分：

當前元素是操作數，直接輸出。當前元素是操作符，執行如下操作：當前元素是左括號，優先級最高，直接進棧。當前元素是右括號，優先級最低，棧頂元素出棧直到遇見左括號。同時消去。只有這種情形，當前元素是不入棧的當前元素是其余操作符棧頂是左括號，當前操作符直接進棧。（之所以需要判斷是因為，我只個+-*/四個字符給了優先級）如果當前元素優先級大于棧頂，入棧。否則，棧頂輸出直到當前元素優先級大于棧頂或者棧為空。最后將棧里元素全部輸出。

代碼

#include <iostream>#include <fstream>#include <string>#include <cctype>#include <stack>#define LOCALint get_PRior(char c){ if( c == '+' || c == '-' ) return 1; else if( c=='*' || c=='/' ) return 2;}int main( void ){#ifdef LOCAL std::ifstream cin("input.dat");#endif int t = 0; cin >> t; while(t--){ std::string infix; cin >> infix; std::string postfix; std::stack<char> stk; int sz = infix.size(); for(int i = 0; i < sz; ++i){ if( std::isspace(infix[i]) ) continue; else if( std::isdigit(infix[i]) ) postfix.push_back(infix[i]); else{ if( stk.empty() ) stk.push(infix[i]); else{ // 當前字符是左括號 if( infix[i] == '(' ) stk.push(infix[i]); // 當前字符是右括號 else if( infix[i] == ')' ){ while(!stk.empty()){ char c = stk.top(); stk.pop(); if( c == '(' ) break; else postfix.push_back(c); } } else{ while(!stk.empty()){ if( stk.top() == '(' ) break; int top_prior = get_prior( stk.top() ); int cur_prior = get_prior( infix[i] ); if( top_prior < cur_prior ) break; else { // 當優先級一樣的時候，從左到右運算，所以先入棧的優先級高 char c = stk.top(); stk.pop(); postfix.push_back( c ); } } stk.push(infix[i]); } } } } while(!stk.empty()){ char c = stk.top(); stk.pop(); postfix.push_back(c); } std::cout << postfix << std::endl; }#ifdef LOCAL cin.close();#endif return 0;}

上一篇：【BZOJ 4521】【CQOI 2016】手機號碼

下一篇：UrlRewritingNet.UrlRewrite 中文文檔