## 文法推导

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}$

### 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

#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

### 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

### 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";
}