Xóa dấu ngoặc đơn dư thừa khỏi biểu thức số học

Question

Đây là câu hỏi phỏng vấn, mà tôi không tìm thấy bất kỳ câu trả lời thỏa đáng nào về stackoverflow hoặc bên ngoài. Báo cáo sự cố:

Đưa ra biểu thức số học, xóa dấu ngoặc đơn thừa. Ví dụ. ((a * b) + c) nên trở thành một * b + c

tôi có thể nghĩ ra một cách rõ ràng của việc chuyển đổi biểu thức trung tố để gửi sửa chữa và chuyển đổi nó trở lại infix - nhưng là có một tốt hơn cách để làm điều này?

Answer 1

Một cặp dấu ngoặc đơn là cần thiết nếu và chỉ khi chúng kèm theo biểu thức chưa được biểu thị của biểu mẫu X% X% ...% X trong đó X là biểu thức hoặc nguyên tử được giữ nguyên và% là toán tử nhị phân một trong các toán tử% có mức ưu tiên thấp hơn so với toán tử được đính kèm trực tiếp vào biểu thức được lồng dấu ở hai bên của nó; hoặc nếu nó là toàn bộ biểu thức. Vì vậy, ví dụ: trong

q * (a * b * c * d) + c 

toán tử xung quanh là {+, *} và toán tử ưu tiên thấp nhất bên trong dấu ngoặc đơn là *, vì vậy dấu ngoặc đơn là không cần thiết. Mặt khác, trong

q * (a * b + c * d) + c 

có toán tử ưu tiên thấp hơn + bên trong dấu ngoặc đơn so với toán tử xung quanh *, vì vậy chúng cần thiết. Tuy nhiên, trong

z * q + (a * b + c * d) + c 

dấu ngoặc đơn là không cần thiết vì bên ngoài * không được đính kèm với biểu thức được kích hoạt. Tại sao điều này đúng là nếu tất cả các toán tử bên trong một biểu thức (X% X% ...% X) có ưu tiên cao hơn một toán tử xung quanh, thì các toán tử bên trong sẽ được tính toán đầu tiên ngay cả khi các dấu ngoặc đơn là đã xóa.

Vì vậy, bạn có thể kiểm tra bất kỳ cặp phù hợp với dấu ngoặc đơn trực tiếp cho dự phòng bằng cách thuật toán này:

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 

Bạn có thể lặp này, loại bỏ cặp dự phòng cho đến khi tất cả các cặp còn lại đều là phòng không dư thừa.

Ví dụ:

((a * b) + c * (e + f)) 

(cặp chế biến từ trái sang phải):

((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 
      ^ ^

cuối cùng kết quả:

a * b + c * (e + f) 

Answer 2

Tôi chỉ tìm ra một câu trả lời:

các cơ sở là:

1. the expression has been tokenized 
2. no syntax error 
3. there are only binary operators 

đầu vào:

list of the tokens, for example: 
    (, (, a, *, b,), +, c,) 

đầu ra:

set of the redundant parentheses pairs (the orders of the pairs are not important), 
for example, 
    0, 8 
    1, 5 

hãy nhận thức được rằng: tập không phải là độc đáo, ví dụ, ((a + b)) * c, chúng tôi có thể xóa dấu ngoặc đơn bên ngoài hoặc dấu bên trong, nhưng biểu thức cuối cùng là duy nhất

cấu trúc dữ liệu:

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 

thuật toán

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 

ví dụ

dụ một

((a*b)+c) 

sau khi quét để b, chúng tôi đã ngăn xếp:

index left_pa min_op left_op 
0 
1  0  
2  1  *  *  <-stack top 

bây giờ chúng tôi gặp đầu tiên ')' (tại pos 5), chúng tôi bật mục

left_pa = 1 
min_op = * 
left_op = * 

và tiền đọc điều hành '+', vì ưu tiên min_op '*'> '+', vì vậy các cặp (1,5) là dư thừa, do đó, đầu ra nó. sau đó quét đến chúng ta gặp nhau cuối cùng ')', vào lúc này, chúng tôi đã ngăn xếp

index left_pa min_op left_op 
0 
1  0  +  + 

chúng tôi bật mục này (kể từ khi chúng ta gặp nhau ')' tại pos 8), và tiền đọc điều hành tiếp theo, kể từ khi có không điều hành và ở chỉ số 0, không có left_op, vì vậy sản lượng cặp (0, 8)

dụ hai

a*(b+c) 

khi chúng ta gặp những ')', chồng cũng giống như:

index left_pa min_op left_op 
0    *  * 
1  2  +  + 

bây giờ, chúng tôi bật mục ở chỉ mục = 1, so sánh min_op '+' với left_op '*' ở chỉ mục 0, chúng tôi có thể tìm ra '(', ')' là cần thiết

Answer 3

Giải pháp này hoạt động nếu biểu thức là hợp lệ. Chúng ta cần ánh xạ các toán tử tới các giá trị ưu tiên.

a.Di chuyển từ hai đầu của mảng để tìm ra dấu ngoặc đơn phù hợp từ cả hai đầu. Cho các chỉ mục là i và j tương ứng.

b. Bây giờ đi qua từ i đến j và tìm ra toán tử ưu tiên thấp nhất không được chứa bên trong bất kỳ dấu ngoặc đơn nào.

c. So sánh mức độ ưu tiên của toán tử này với toán tử bên trái dấu ngoặc đơn mở và bên phải của dấu ngoặc đơn. Nếu không có toán tử nào tồn tại, hãy coi ưu tiên của nó là -1. Nếu mức độ ưu tiên của toán tử cao hơn hai giá trị này, hãy xóa dấu ngoặc đơn tại i và j.

d. Tiếp tục các bước từ a đến c cho đến khi tôi < = j.

Answer 4

1. Đẩy một mục trống trong ngăn xếp

2. Quét danh sách thẻ

   2.1 nếu token là toán hạng, bỏ qua.

   2.2 nếu mã thông báo là nhà điều hành, ghi lại các nhà điều hành trong left_op, nếu min_op là con số không, thiết lập min_op = toán tử này, nếu min_op không phải là con số không, so sánh min_op với nhà điều hành này, thiết lập min_op như một trong hai toán tử có mức độ ưu tiên thấp hơn.

   2.3 nếu mã thông báo bị để lại parenthese, hãy đẩy một mục trong ngăn xếp, với left_pa = vị trí của dấu ngoặc đơn.

   2.4 nếu token là ngoặc đúng:

   2.4.1 chúng ta có cặp ngoặc (left_pa và ngoặc đúng)

   2.4.2 bật mục

   2.4. 3 mã thông báo tiếp theo được đọc trước, nếu đó là một toán tử, hãy đặt nó làm toán tử bên phải

   2.4.4 so sánh min_op của mục với left_op và toán tử phải (nếu có m tồn tại), chúng ta có thể dễ dàng biết nếu cặp của dấu ngoặc đơn thừa và xuất nó (nếu min_op < bất kỳ toán tử left_op và right nào, dấu ngoặc đơn là cần thiết, nếu min_op = left_op, dấu ngoặc đơn là cần thiết, nếu không dư thừa)

   2.4.5 nếu không có left_op và không điều hành phải (mà cũng có nghĩa min_op = nil) và chồng là không có sản phẩm nào, thiết lập min_op hàng đầu mục như min_op của popped-up item ví dụ

Answer 5

Mã dưới đây là một giải pháp đơn giản, được giới hạn ở +-*/; nếu bạn muốn bạn có thể thêm chúng theo yêu cầu của bạn.

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

Answer 6

Tôi nghĩ rằng bạn đang tìm kiếm loại thuật toán như được thấy trong ảnh sau.

Thuật toán này "gần như" đã sẵn sàng, vì rất nhiều lỗi phát sinh một khi phức tạp trở nên phức tạp hơn, nó trở nên phức tạp hơn.Cách tôi làm việc trên điều này, là 'xây dựng và viết-mã-on-the-fly', có nghĩa là cho đến 4 dấu ngoặc đơn, mọi thứ rất dễ dàng. Nhưng sau khi biểu hiện trở nên phức tạp hơn, có những thứ mà tôi không thể dự đoán được khi viết ra những suy nghĩ trên giấy. Và có trình biên dịch cho tôi biết những gì cần sửa. Nó sẽ không phải là một lời nói dối nếu tôi nói rằng nó không phải là tôi đã viết các thuật toán, nhưng trình biên dịch (C#) để thay thế! Cho đến nay, nó đã cho tôi 1400 dòng. Nó không phải là các lệnh khó viết. Đó là sự sắp xếp của họ, đó là một câu đố thực sự. Chương trình này bạn đang tìm kiếm, được đặc trưng bởi một mức độ phức tạp thực sự cao. Vâng, nếu bạn cần bất kỳ ý tưởng chính, xin vui lòng cho tôi biết và tôi sẽ trả lời. Thanx!

Algorithm