Это вопрос интервью, для которого я не нашел удовлетворительных ответов на stackoverflow или снаружи. Описание проблемы:
Учитывая арифметическое выражение, удалите лишние круглые скобки. Например. ((a * b) + c) должно стать a * b + c
Я могу представить себе очевидный способ преобразования выражения infix в post fix и преобразования его обратно в infix - но есть ли лучший способ сделать это?
Пара круглых скобок необходима тогда и только тогда, когда они заключают несвязанное выражение вида X% X%...% X, где X - либо выраженные в скобках выражения или атомы, а% - бинарные операторы, и если хотя бы один операторов% имеет более низкий приоритет, чем оператор, прикрепленный непосредственно к заключенному в скобки выражению по обе стороны от него; или если это все выражение. Так, например, в
q * (a * b * c * d) + c
окружающие операторы являются {+, *}, а оператор с наименьшим приоритетом внутри круглых скобок равен *, поэтому скобки не нужны. С другой стороны, в
q * (a * b + c * d) + c
в круглых скобках есть оператор меньшего приоритета +, чем окружающий оператор *, поэтому они необходимы. Однако в
z * q + (a * b + c * d) + c
скобки не нужны, поскольку внешний * не привязан к выражению в скобках.
Почему это так: если все операторы внутри выражения (X% X%...% X) имеют более высокий приоритет, чем окружающий оператор, тогда внутренние операторы в любом случае рассчитываются сначала, даже если скобки удалены.
Итак, вы можете проверить любую пару совпадающих скобок непосредственно для избыточности по этому алгоритму:
Let L be operator immediately left of the left parenthesis, or nil
Let R be operator immediately right of the right parenthesis, or nil
If L is nil and R is nil:
Redundant
Else:
Scan the unparenthesized operators between the parentheses
Let X be the lowest priority operator
If X has lower priority than L or R:
Not redundant
Else:
Redundant
Вы можете выполнить итерацию, удалив избыточные пары, пока все оставшиеся пары не будут избыточными.
Пример:
((a * b) + c * (e + f))
(Обработка пар слева направо):
((a * b) + c * (e + f)) L = nil R = nil --> Redundant
^ ^
(a * b) + c * (e + f) L = nil R = nil --> Redundant
^ ^ L = nil R = + X = * --> Redundant
a * b + c * (e + f) L = * R = nil X = + --> Not redundant
^ ^
Конечный результат:
a * b + c * (e + f)
Я только что понял ответ:
:
1. the expression has been tokenized
2. no syntax error
3. there are only binary operators
:
list of the tokens, for example:
(, (, a, *, b, ), +, c, )
выход:
set of the redundant parentheses pairs (the orders of the pairs are not important),
for example,
0, 8
1, 5
пожалуйста, помните об этом: набор не уникален, например, ((a + b)) * c, мы можем удалить внешние скобки или внутренние, но окончательное выражение уникально
структура данных:
a stack, each item records information in each parenthese pair
the struct is:
left_pa: records the position of the left parenthese
min_op: records the operator in the parentheses with minimum priority
left_op: records current operator
алгоритм
1.push one empty item in the stack
2.scan the token list
2.1 if the token is operand, ignore
2.2 if the token is operator, records the operator in the left_op,
if min_op is nil, set the min_op = this operator, if the min_op
is not nil, compare the min_op with this operator, set min_op as
one of the two operators with less priority
2.3 if the token is left parenthese, push one item in the stack,
with left_pa = position of the parenthese
2.4 if the token is right parenthese,
2.4.1 we have the pair of the parentheses(left_pa and the
right parenthese)
2.4.2 pop the item
2.4.3 pre-read next token, if it is an operator, set it
as right operator
2.4.4 compare min_op of the item with left_op and right operator
(if any of them exists), we can easily get to know if the pair
of the parentheses is redundant, and output it(if the min_op
< any of left_op and right operator, the parentheses are necessary,
if min_op = left_op, the parentheses are necessary, otherwise
redundant)
2.4.5 if there is no left_op and no right operator(which also means
min_op = nil) and the stack is not empty, set the min_op of top
item as the min_op of the popped-up item
примеры
пример один
((a*b)+c)
после сканирования до b, у нас есть стек:
index left_pa min_op left_op
0
1 0
2 1 * * <-stack top
теперь мы встречаем первый ')' (в позиции 5), мы выставляем элемент
left_pa = 1
min_op = *
left_op = *
и предварительно прочитанный оператор '+', так как min_op priority '*' > '+', поэтому пара (1,5) избыточна, поэтому выведите его. затем сканируйте, пока мы не встретим последний ')', на данный момент у нас есть стек
index left_pa min_op left_op
0
1 0 + +
мы выставляем этот элемент (поскольку мы встречаемся ')' в позиции 8) и предварительно читаем следующий оператор, так как нет оператора и с индексом 0 нет left_op, поэтому выведите пару (0, 8)
пример два
a*(b+c)
когда мы встречаем ')', стек выглядит так:
index left_pa min_op left_op
0 * *
1 2 + +
теперь мы выставляем элемент по индексу = 1, сравниваем min_op '+' с left_op '*' с индексом 0, мы можем узнать, что '(', ')' необходимы
Сканировать список маркеров
2.1, если токен является операндом, игнорировать.
2.2, если токен является оператором, записывает оператор в left_op, если min_op равно nil, установите min_op = этот оператор, если min_op не равен нулю, сравните min_op с этим оператором, установите min_op как один из двух операторов с меньшим приоритетом.
2.3, если токен оставлен в поле parenthese, нажмите один элемент в стеке, с left_pa = положением скобок.
2.4, если токен - это правильная скобка:
2.4.1 у нас есть пара скобок (left_pa и правая скобка)
2.4.2 поместите элемент
2.4.3 предварительно прочитанный следующий токен, если он является оператором, установите его как правый оператор
2.4.4 сравнить min_op элемента с left_op и правым оператором (если любой из них существует), мы можем легко узнать, если пара круглых скобок является избыточным и выводит его (если min_op < любой из left_op и правого оператора, скобки необходимы, если min_op = left_op, скобки необходимы, иначе избыточный)
2.4.5, если нет left_op и никакого правильного оператора (что также означает min_op = nil), и стек не пуст, установите min_op сверху item как min_op всплывающего элемента примеры
Эти решения работают, если выражение является действительным. Нам нужно сопоставить операторы с приоритетными значениями.
а. Пройдите с двух концов массива, чтобы определить совпадающие скобки с обоих концов. Пусть индексы равны я и j соответственно.
б. Теперь переходим от я к j и обнаруживаем оператор наименьшего приоритета, который не содержится внутри каких-либо круглых скобок.
с. Сравните приоритет этого оператора с операторами слева от открытой круглой скобки и справа от закрытия круглых скобок. Если такой оператор не существует, относите его приоритет как -1. Если приоритет оператора выше этих двух, удалите скобки в я и j.
д. Продолжайте шаги a до c, пока я <= j.
Нижеприведенный код - это простое решение, ограниченное +-*/; если вы хотите, вы можете добавить их в соответствии с вашими требованиями.
#include <iostream>
#include <stack>
#include <set>
using namespace std;
int size;
int loc;
set<char> support;
string parser(string input , int _loc){
string expi;
set<char> op;
loc = _loc;
while(1){
if(input[loc] == '('){
expi += parser(input,loc+1);
}else if(input[loc] == ')'){
if((input[loc+1] != '*') && (input[loc+1] != '/')){
return expi;
}else{
if ((op.find('+') == op.end()) && (op.find('-') == op.end())){
return expi;
}else{
return '('+expi+')';
}
}
}else{
char temp = input[loc];
expi=expi+temp;
if(support.find(temp) != support.end()){
op.insert(temp);
}
}
loc++;
if(loc >= size){
break;
}
}
return expi;
}
int main(){
support.insert('+');
support.insert('-');
support.insert('*');
support.insert('/');
string input("(((a)+((b*c)))+(d*(f*g)))");
//cin >> input;
size = input.size();
cout<<parser(input,0);
return 0;
}
Я думаю, что вы ищете какой-то алгоритм, как показано на следующем рисунке.
Этот алгоритм "почти" готов, так как возникает много ошибок, когда они становятся более сложными, тем сложнее он получается. То, как я работаю над этим, - это "сборка и запись кода на лету", что означает, что для до четырех круглых скобок все очень просто. Но после того, как выражение становится более сложным, есть вещи, которые я не могу предсказать, записывая мысли на бумаге. И приходит компилятор, чтобы сказать мне, что исправить. Было бы неправдой, если бы я заявлял, что это не я написал алгоритм, а компилятор (С#) вместо этого! Пока это заняло 1400 строк. Дело не в том, что командам было сложно писать. Это была их договоренность, которая была настоящей загадкой. Эта программа, которую вы ищете, характеризуется действительно высоким уровнем сложности. Ну, если вам нужны какие-то основные идеи, пожалуйста, дайте мне знать, и я отвечу. Thanx!