CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
文法推导
Time Limit: 1sec Memory Limit: 256MB
Description
\[E\to TE' \\ E'\to +TE' \vert \epsilon \\ T\to FT' \\ T'\to *FT' \vert \epsilon \\ F\to (E) \vert \mathbf{id}\]依据教材第 4.4 节文法 4.28，将其中的 $\mathbf{id}$ 替换为 0 到 9 的数字，对于输入的字符串，输出其最左推导的过程。如果输入的字符串不符合文法的定义，则输出”Syntax Error”。
Input
有多组测试数据，每组数据一行，包含一个字符串，字符串只包含有文法中的终端符号。字符串长度不超过 100。
输入以#号结束。
Output
对于每组数据，如果输入字符串符合文法的定义，输出其最左推导的过程，每步推导占一行；否则，输出「Syntax Error」。每组数据输出结束后再输出一个空行。
Sample Input
3+5*0
1*2*
#
Sample Output
E
TE'
FT'E'
3T'E'
3E'
3+TE'
3+FT'E'
3+5T'E'
3+5*FT'E'
3+5*0T'E'
3+5*0E'
3+5*0
Syntax Error
Solution
因为看漏了文法中的括号，导致无限 WA、RE、TLE…老年人该看看眼睛了。
#include <bits/stdc++.h>
#define SE "Syntax Error\n"
using namespace std;
struct Rule
{
char prefix, eps, id;
string lc, rc;
};
string work(const char *b, const char *e, string r)
{
static map<string, Rule> mp{
{"E", {0, 0, 0, "T", "E'"}},
{"E'", {'+', 1, 0, "T", "E'"}},
{"T", {0, 0, 0, "F", "T'"}},
{"T'", {'*', 1, 0, "F", "T'"}},
{"F", {0, 0, 1, "E", "E"}}};
if (mp[r].id)
{
if (e - b == 1 && isdigit(*b))
return r + "\n" + string(1, *b) + "\n";
if (e - b < 2 || *b != '(' || *(e - 1) != ')')
return SE;
string s = work(b + 1, e - 1, mp[r].lc);
if (s == SE)
return SE;
string ans = r + "\n";
for (int p = 0, q = 0; q < s.size(); ++q)
if (s[q] == '\n')
{
ans += "(" + s.substr(p, q - p) + ")\n";
p = q + 1;
}
return ans;
}
if (e - b == 0 && mp[r].eps)
return r + "\n\n";
if (e - b == 0 && mp[r].prefix)
return SE;
if (e - b && mp[r].prefix && mp[r].prefix != *b)
return SE;
for (int i = (mp[r].prefix ? 1 : 0); i <= e - b; ++i)
{
string lc = work(mp[r].prefix ? b + 1 : b, b + i, mp[r].lc);
if (lc == SE)
continue;
string rc = work(b + i, e, mp[r].rc);
if (rc == SE)
continue;
string ans = (mp[r].prefix ? string(1, mp[r].prefix) : "") + r + "\n", last;
for (int p = 0, q = 0; q < lc.size(); ++q)
if (lc[q] == '\n')
{
last = (mp[r].prefix ? string(1, mp[r].prefix) : "") + lc.substr(p, q - p);
ans += last + mp[r].rc + "\n";
p = q + 1;
}
for (int p = 0, q = 0, first = 0; q < rc.size(); ++q)
if (rc[q] == '\n')
{
if (first)
ans += last + rc.substr(p, q - p) + "\n";
else
first = 1;
p = q + 1;
}
return ans;
}
return SE;
}
int main()
{
for (char s[127]; scanf("%s", s) != EOF && strcmp("#", s);)
cout << work(s, s + strlen(s), "E") << "\n";
}
中缀转后缀
Time Limit: 1sec Memory Limit: 256MB
Description
输入一个中缀算术表达式 S，S 中的操作数为 0 到 9，只含+，-和*，/运算，也可能含有括号()，运算符的计算顺序和实际四则运算的计算顺序相同. 请输出与 S 等价的后缀表达式，注意输出结果不要含有多余的括号或空格.
Input
输入有多组数据.
每组数据是一个中缀表达式 S，S 的长度不超过 50. 输入的 S 保证合法，而且不包含多余的空格或制表符.
输入以#号结束.
Output
对于每个中缀表达式，输出转换后的后缀表达式，每个输出占一行.
Sample Input
1
1+2*3
(1-2)/3
#
Sample Output
1
123*+
12-3/
Solution
#include <bits/stdc++.h>
using namespace std;
vector<string> s_to_infix(const string &s)
{
vector<string> ans;
for (int i = 0; i < s.size(); ++i)
{
ans.push_back("");
if (isdigit(s[i]))
{
for (; i < s.size() && isdigit(s[i]); ++i)
ans.back() += s[i];
--i;
continue;
}
ans.back() += s[i];
}
return ans;
}
vector<string> infix_to_suffix(const vector<string> &v)
{
vector<string> ans, op;
for (auto &s : v)
{
if (isdigit(s.back()))
ans.push_back(s);
else if (op.empty() || s == "(")
op.push_back(s);
else if (s == ")")
{
for (; op.back() != "("; op.pop_back())
ans.push_back(op.back());
op.pop_back();
}
else
{
for (; !op.empty() && op.back() != "(" && (op.back() != "+" && op.back() != "-" || s != "*" && s != "/"); op.pop_back())
ans.push_back(op.back());
op.push_back(s);
}
}
ans.insert(ans.end(), op.rbegin(), op.rend());
return ans;
}
int main()
{
for (string s; cin >> s && s != "#"; cout << "\n")
for (auto &t : infix_to_suffix(s_to_infix(s)))
cout << t;
}
表达式求值
Time Limit: 1sec Memory Limit: 256MB
Description
输入中缀算术表达式 S，S 中的操作数为非负整数，只含+，-和*，/运算，也可能含有括号()，运算符的计算顺序和实际四则运算的计算顺序相同. 输出表达式 S 的值. 注意除法运算只取整数部分，例如 1/2=0.
Input
输入有多组数据.
每组数据是一个算术表达式 S，S 的长度不超过 100. 输入的 S 保证合法，而且不包含多余的空格或制表符. S 的操作数、中间结果和最终结果都不会超过 int 类型的范围，也不会出现除数为 0 的情况.
输入以#号结束.
Output
对于每个算术表达式 S，输出 S 的值，每个输出占一行.
Sample Input
1
478+522
(478+522)*10
1/2-1
#
Sample Output
1
1000
10000
-1
Solution
代 码 复 用
#include <bits/stdc++.h>
using namespace std;
vector<string> s_to_infix(const string &s)
{
vector<string> ans;
for (int i = 0; i < s.size(); ++i)
{
ans.push_back("");
if (isdigit(s[i]))
{
for (; i < s.size() && isdigit(s[i]); ++i)
ans.back() += s[i];
--i;
continue;
}
ans.back() += s[i];
}
return ans;
}
vector<string> infix_to_suffix(const vector<string> &v)
{
vector<string> ans, op;
for (auto &s : v)
{
if (isdigit(s.back()))
ans.push_back(s);
else if (op.empty() || s == "(")
op.push_back(s);
else if (s == ")")
{
for (; op.back() != "("; op.pop_back())
ans.push_back(op.back());
op.pop_back();
}
else
{
for (; !op.empty() && op.back() != "(" && (op.back() != "+" && op.back() != "-" || s != "*" && s != "/"); op.pop_back())
ans.push_back(op.back());
op.push_back(s);
}
}
ans.insert(ans.end(), op.rbegin(), op.rend());
return ans;
}
int postfix_to_int(const vector<string> &v)
{
vector<int> stak;
for (auto &s : v)
{
if (isdigit(s[0]))
{
stak.push_back(stoi(s));
continue;
}
int b = stak.back();
stak.pop_back();
int a = stak.back();
stak.back() = s == "+" ? a + b : s == "-" ? a - b : s == "*" ? a * b : a / b;
}
return stak.back();
}
int main()
{
for (string s; cin >> s && s != "#";)
cout << postfix_to_int(infix_to_suffix(s_to_infix(s))) << "\n";
}