接尾辞式の変換接尾辞式および接尾辞式の値の計算(C++)
3709 ワード
1.接尾辞を接尾辞に変換するポイント(1)数字に遭遇した場合は直接出力する必要がありますが、数字が1桁だけではない場合があるため、式を巡回して値を取得する必要があります.(2)演算子スタックが空の場合、演算子に遭遇した場合、直接スタックに入る.(3)「(」に遭遇した場合、直接にスタックに入る.(4)「)」に遭遇した場合、スタックの一番上の要素が「(」であるまでスタックを連続的に出て、それから「(」である.(5)演算子に遭遇し、演算子スタックが空でない場合、現在の演算子とスタックの一番上の演算子の優先度を比較する必要がある.2つの状況に分けられる:1.現在の演算子の優先度はスタックトップ演算子の優先度より大きく、直接スタックに入ります.2.現在の演算子はスタックトップ演算子より優先され、スタックトップ演算子が現在の演算子より優先されるまでスタックを出て、現在の演算子をスタックに入れる必要があります.
2.コード実装
2.コード実装
#include
#include
#include
#include
#include
using namespace std;
#define ERROR 0x3f3f
string cto_string(char c) {
stringstream stream;
stream << c;
return stream.str();
}
int cmp(char a, char b) {
if (a=='+') {
if (b == '-' || b == '+') return 0;
else if (b == '*' || b == '/') return -1;
else if (b == '(') return 1;
} else if (a == '-') {
if (b == '-' || b == '+') return 0;
else if (b == '*' || b == '/') return -1;
else if (b == '(') return 1;
} else if (a == '*') {
if (b == '*' || b == '/') return 0;
else if(b == '+' || b == '-' || b == '(') return 1;
} else if (a == '/') {
if (b == '*' || b == '/') return 0;
else if(b == '+' || b == '-' || b == '(') return 1;
} else {
cout << "invalid sign" << endl;
return ERROR;
}
}
vector res;
vector InfixToSuffix(string infix) {
stack st;
int i = 0;
while (i < infix.length()) {
if (infix[i] == '(') {
st.push(infix[i]);
i ++;
} else if (infix[i] == ')') {
while (!st.empty()) {
char op = st.top();st.pop();
if (op == '(') break;
else res.push_back(cto_string(op));
i ++;
}
} else if (isdigit(infix[i])) {
int n = infix[i ++] - '0';
while (i < infix.length() && isdigit(infix[i])) {
n = n * 10 + (infix[i ++] - '0');
}
res.push_back(to_string(n));
} else {
if (st.empty()) st.push(infix[i]);
else {
if (cmp(infix[i], st.top()) > 0) st.push(infix[i]);
else if (cmp(infix[i], st.top()) <= 0) {
while (!st.empty()) {
char op = st.top();st.pop();
res.push_back(cto_string(op));
if (cmp(infix[i], op) > 0) break;
}
st.push(infix[i]);
}
}
i ++;
}
}
while (!st.empty()) {
res.push_back(cto_string(st.top())); st.pop();
}
return res;
}
//
int calculate(vector& a) {
stack st;
for (auto x : a) {
if (x == "+") {
int a = st.top();st.pop();
int b = st.top();st.pop();
st.push(b + a);
}
else if (x == "-") {
int a = st.top();st.pop();
int b = st.top();st.pop();
st.push(b - a);
}
else if (x == "*") {
int a = st.top();st.pop();
int b = st.top();st.pop();
st.push(b * a);
}
else if (x == "/") {
int a = st.top();st.pop();
int b = st.top();st.pop();
st.push(b / a);
}
else {
st.push(stoi(x));
}
}
return st.top();
}
void print(string a) {cout << a << " ";}
int main() {;
string s;
cin >> s;
vector t = InfixToSuffix(s);
for_each(t.begin(), t.end(), print);cout << endl;
int ans = calculate(t);
cout << ans << endl;
return 0;
}