Илэрхийлэл задлан шинжлэх¶
Тоо ба төрөл бүрийн оператор агуулсан математик илэрхийлэл бүхий тэмдэгт мөр өгөгдсөн. Бид түүний утгыг $O(n)$-д тооцоолох ёстой, энд $n$ нь тэмдэгт мөрийн урт юм.
Энд авч үзэх алгоритм нь илэрхийллийг урвуу Польш тэмдэглэгээ гэж нэрлэгддэг хэлбэрт (ил эсвэл далд байдлаар) хөрвүүлж, энэ илэрхийллийг тооцоолно.
Урвуу Польш тэмдэглэгээ¶
Урвуу Польш тэмдэглэгээ гэдэг нь операторууд нь өөрсдийн операндуудын дараа байрладаг математик илэрхийлэл бичих хэлбэр юм. Жишээ нь дараах илэрхийллийг
урвуу Польш тэмдэглэгээгээр дараах байдлаар бичиж болно:
Урвуу Польш тэмдэглэгээг Австралийн философич, компьютерийн ухааны мэргэжилтэн Charles Hamblin 1950-иад оны дунд үед, Польшийн математикч Jan Łukasiewicz-ийн 1920 онд санал болгосон Польш тэмдэглэгээн дээр үндэслэн боловсруулсан.
Урвуу Польш тэмдэглэгээний давуу тал нь энэ хэлбэрийн илэрхийллийг шугаман хугацаанд тооцоолоход маш амархан явдал юм. Бид эхэндээ хоосон байх стек ашиглана. Бид урвуу Польш тэмдэглэгээ дэх илэрхийллийн операнд ба операторуудыг гүйнэ. Хэрэв одоогийн элемент тоо бол бид утгыг стекийн оройд тавина, хэрэв одоогийн элемент оператор бол бид стекээс дээд хоёр элементийг авч, үйлдлийг гүйцэтгээд, үр дүнг стекийн оройд буцаан тавина. Эцэст нь стект яг нэг элемент үлдэх бөгөөд энэ нь илэрхийллийн утга байх болно.
Энэ энгийн тооцоолол $O(n)$ хугацаанд ажиллах нь илэрхий.
Энгийн илэрхийллийг задлан шинжлэх¶
Одоохондоо бид зөвхөн хялбарчилсан бодлогыг авч үзнэ: бид бүх оператор хоёрлосон (өөрөөр хэлбэл хоёр аргумент авдаг) бөгөөд бүгд left-associative (хэрэв тэргүүлэх эрх тэнцүү бол зүүнээс баруун тийш гүйцэтгэгдэнэ) гэж үзнэ. Хаалт зөвшөөрөгдөнө.
Бид хоёр стек тохируулна: нэг нь тоонд, нөгөө нь оператор ба хаалтад зориулагдана. Эхэндээ хоёр стек хоёулаа хоосон байна. Хоёр дахь стекийн хувьд бид бүх үйлдэл чанд буурах тэргүүлэх эрхээр эрэмбэлэгдсэн байх нөхцөлийг хадгална. Хэрэв стект хаалт байвал операторын блок бүр (нэг хос хаалтад харгалзах) эрэмбэлэгдсэн байх ба бүхэл стек эрэмбэлэгдсэн байх албагүй.
Бид илэрхийллийн тэмдэгтүүдийг зүүнээс баруун тийш гүйнэ. Хэрэв одоогийн тэмдэгт цифр бол бид энэ тооны утгыг стект тавина. Хэрэв одоогийн тэмдэгт нээх хаалт бол бид түүнийг стект тавина. Хэрэв одоогийн тэмдэгт хаах хаалт бол бид нээх хаалтад хүртэл стек дэх бүх операторыг гүйцэтгэнэ (өөрөөр хэлбэл бид хаалтан доторх бүх үйлдлийг гүйцэтгэнэ). Эцэст нь хэрэв одоогийн тэмдэгт оператор бол стекийн орой ижил буюу илүү өндөр тэргүүлэх эрхтэй оператортой байх хооронд бид энэ үйлдлийг гүйцэтгэж, шинэ үйлдлийг стект тавина.
Бид бүхэл тэмдэгт мөрийг боловсруулсны дараа зарим оператор стект үлдсэн байж болох тул бид тэдгээрийг гүйцэтгэнэ.
$+$ $-$ $*$ $/$ гэсэн дөрвөн операторын хувьд энэ аргын хэрэгжүүлэлт энд байна:
bool delim(char c) {
return c == ' ';
}
bool is_op(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
int priority (char op) {
if (op == '+' || op == '-')
return 1;
if (op == '*' || op == '/')
return 2;
return -1;
}
void process_op(stack<int>& st, char op) {
int r = st.top(); st.pop();
int l = st.top(); st.pop();
switch (op) {
case '+': st.push(l + r); break;
case '-': st.push(l - r); break;
case '*': st.push(l * r); break;
case '/': st.push(l / r); break;
}
}
int evaluate(string& s) {
stack<int> st;
stack<char> op;
for (int i = 0; i < (int)s.size(); i++) {
if (delim(s[i]))
continue;
if (s[i] == '(') {
op.push('(');
} else if (s[i] == ')') {
while (op.top() != '(') {
process_op(st, op.top());
op.pop();
}
op.pop();
} else if (is_op(s[i])) {
char cur_op = s[i];
while (!op.empty() && priority(op.top()) >= priority(cur_op)) {
process_op(st, op.top());
op.pop();
}
op.push(cur_op);
} else {
int number = 0;
while (i < (int)s.size() && isalnum(s[i]))
number = number * 10 + s[i++] - '0';
--i;
st.push(number);
}
}
while (!op.empty()) {
process_op(st, op.top());
op.pop();
}
return st.top();
}
Ингэснээр бид илэрхийллийн утгыг $O(n)$-д хэрхэн тооцоолохыг сурсан бөгөөд үүний зэрэгцээ бид урвуу Польш тэмдэглэгээг далд байдлаар ашигласан. Дээрх хэрэгжүүлэлтийг бага зэрэг өөрчилснөөр илэрхийллийг урвуу Польш тэмдэглэгээгээр ил хэлбэрээр авах боломжтой.
Нэг аргументтай оператор¶
Одоо илэрхийлэл нь нэг аргументтай оператор (нэг аргумент авдаг оператор) мөн агуулж байг гэж бодъё. Нэг аргументтай нэмэх ба нэг аргументтай хасах нь ийм операторын түгээмэл жишээ юм.
Энэ тохиолдлын нэг ялгаа нь одоогийн оператор нэг аргументтай эсвэл хоёрлосон эсэхийг бид тодорхойлох хэрэгтэй явдал юм.
Нэг аргументтай операторын өмнө үргэлж өөр оператор эсвэл нээх хаалт байдаг, эсвэл огт юу ч байдаггүйг (хэрэв энэ нь илэрхийллийн хамгийн эхэнд байвал) та анзаарч болно. Эсрэгээрээ хоёрлосон операторын өмнө үргэлж операнд (тоо) эсвэл хаах хаалт байна. Тиймээс дараагийн оператор нэг аргументтай байж чадах эсэхийг тэмдэглэхэд амархан.
Түүнчлэн бид нэг аргументтай ба хоёрлосон операторыг өөр өөрөөр гүйцэтгэх хэрэгтэй. Мөн бид нэг аргументтай операторын тэргүүлэх эрхийг бүх хоёрлосон операторынхоос өндөр сонгох хэрэгтэй.
Нэмж дурдахад зарим нэг аргументтай оператор (жишээ нь нэг аргументтай нэмэх ба нэг аргументтай хасах) үнэндээ right-associative болохыг тэмдэглэх нь зүйтэй.
Right-associativity¶
Right-associative гэдэг нь тэргүүлэх эрх тэнцүү үед операторуудыг баруунаас зүүн тийш тооцоолох ёстой гэсэн үг юм.
Дээр тэмдэглэсэнчлэн нэг аргументтай операторууд ихэвчлэн right-associative байдаг. Right-associative операторын өөр нэг жишээ бол зэрэгт дэвшүүлэх оператор юм ($a \wedge b \wedge c$-г ихэвчлэн $(a^b)^c$ биш $a^{b^c}$ гэж ойлгодог).
Right-associative операторыг зөв зохицуулахын тулд бид ямар ялгаа гаргах хэрэгтэй вэ? Өөрчлөлт нь маш бага байх нь тогтоогддог. Цорын ганц ялгаа нь тэргүүлэх эрх тэнцүү бол бид right-associative үйлдлийн гүйцэтгэлийг хойшлуулах явдал юм.
Солих шаардлагатай цорын ганц мөр бол
while (!op.empty() && priority(op.top()) >= priority(cur_op))
while (!op.empty() && (
(left_assoc(cur_op) && priority(op.top()) >= priority(cur_op)) ||
(!left_assoc(cur_op) && priority(op.top()) > priority(cur_op))
))
left_assoc нь оператор left-associative эсэхийг шийддэг функц юм.
$+$ $-$ $*$ $/$ хоёрлосон операторууд ба $+$, $-$ нэг аргументтай операторуудын хэрэгжүүлэлт энд байна.
bool delim(char c) {
return c == ' ';
}
bool is_op(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
bool is_unary(char c) {
return c == '+' || c=='-';
}
int priority (char op) {
if (op < 0) // unary operator
return 3;
if (op == '+' || op == '-')
return 1;
if (op == '*' || op == '/')
return 2;
return -1;
}
void process_op(stack<int>& st, char op) {
if (op < 0) {
int l = st.top(); st.pop();
switch (-op) {
case '+': st.push(l); break;
case '-': st.push(-l); break;
}
} else {
int r = st.top(); st.pop();
int l = st.top(); st.pop();
switch (op) {
case '+': st.push(l + r); break;
case '-': st.push(l - r); break;
case '*': st.push(l * r); break;
case '/': st.push(l / r); break;
}
}
}
int evaluate(string& s) {
stack<int> st;
stack<char> op;
bool may_be_unary = true;
for (int i = 0; i < (int)s.size(); i++) {
if (delim(s[i]))
continue;
if (s[i] == '(') {
op.push('(');
may_be_unary = true;
} else if (s[i] == ')') {
while (op.top() != '(') {
process_op(st, op.top());
op.pop();
}
op.pop();
may_be_unary = false;
} else if (is_op(s[i])) {
char cur_op = s[i];
if (may_be_unary && is_unary(cur_op))
cur_op = -cur_op;
while (!op.empty() && (
(cur_op >= 0 && priority(op.top()) >= priority(cur_op)) ||
(cur_op < 0 && priority(op.top()) > priority(cur_op))
)) {
process_op(st, op.top());
op.pop();
}
op.push(cur_op);
may_be_unary = true;
} else {
int number = 0;
while (i < (int)s.size() && isalnum(s[i]))
number = number * 10 + s[i++] - '0';
--i;
st.push(number);
may_be_unary = false;
}
}
while (!op.empty()) {
process_op(st, op.top());
op.pop();
}
return st.top();
}