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 中文文档