NWPU 数据结构 NOJ 008 逆波兰表达式

https://en.wikipedia.org/wiki/Shunting_yard_algorithm

使用调度场算法,维基百科图示如下

本题目需要特殊处理括号的优先级,代码:

#include <bits/stdc++.h> using namespace std; int PRT[300]; int main() { // freopen("008.in", "r", stdin); string eval; getline(cin, eval); string t = ""; stack<char> op; queue<char> q; PRT['*'] = PRT['/'] = 1; PRT['+'] = PRT['-'] = 2; for(int i = 0; i < eval.length(); i++) { char c = eval[i]; if(c == ' ') continue; // cout << "[" << c << "] " << endl; if(isalpha(c)) { t += c; continue; } if(c == '(') { op.push(c); continue; } if(c == ')') { while(!op.empty()) { char _ = op.top(); op.pop(); if(_ == '(') { break; } t += _; } continue; } while(!op.empty()) { char _ = op.top(); if(PRT[_] <= PRT[c] && _ != '(') { t += _; op.pop(); } else { break; } } op.push(c); } while(!op.empty()) { t += op.top(); op.pop(); } cout << t << endl; return 0; }
Code language: PHP (php)

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注