Trình phân tích cú pháp biểu thức bậc ba trong C ++

Giả sử chúng ta có một chuỗi biểu diễn các biểu thức bậc ba lồng nhau tùy ý, chúng ta phải tính kết quả của biểu thức. chúng ta luôn có thể giả định rằng biểu thức đã cho là hợp lệ và chỉ bao gồm các chữ số 0-9,?,:, T và F vài ký tự này. (Ở đây T và F đại diện cho True và False tương ứng). Có một số thuộc tính -

Độ dài của chuỗi đã cho phải nhỏ hơn hoặc bằng 10000.
Mỗi số chỉ chứa một chữ số.
Nhóm biểu thức điều kiện từ phải sang trái.
Điều kiện sẽ luôn là T hoặc F. Vì vậy, điều kiện sẽ không bao giờ là một chữ số.
Kết quả của biểu thức sẽ luôn đánh giá thành chữ số 0-9, T hoặc F.

Vì vậy, ví dụ:nếu đầu vào là “F? 1:T? 4:5”, thì đầu ra sẽ là 4, vì nó sẽ phân tích cú pháp biểu thức ngoài cùng bên phải “T? 4:5”, nó sẽ trả về 4, sau đó biểu thức chính sẽ là “F? 1:4”, vì vậy giá trị trả về là 4.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

ret:=một chuỗi trống, n:=kích thước của s, tạo một ngăn xếp
cho tôi trong phạm vi n - 1 xuống 0
- x:=s [i]
- nếu st không trống và trên cùng của ngăn xếp là ‘?’, thì
  - xóa khỏi st
  - đầu tiên:=top of st, sau đó xóa hai phần tử khỏi ngăn xếp
  - thứ hai:=trên cùng của ngăn xếp và xóa khỏi st
  - nếu x là T thì chèn đầu tiên vào st, nếu không thì chèn thứ hai vào st
- nếu không, hãy chèn x vào st
trong khi st không trống, thì
- ret:=ret + top of st và xóa khỏi st
đảo ngược ret và trả lại ret

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   string parseTernary(string s) {
      string ret = "";
      int n = s.size();
      stack <char> st;
      for(int i = n - 1; i >= 0; i--){
         char x = s[i];
         if(!st.empty() && st.top() == '?'){
            st.pop();
            char first = st.top();
            st.pop();
            st.pop();
            char second = st.top();
            st.pop();
            if(x == 'T'){
               st.push(first);
            }
            else st.push(second);
            }
            else{
               st.push(x);
            }
         }
         while(!st.empty()){
            ret += st.top();
            st.pop();
         }
         reverse(ret.begin(), ret.end());
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.parseTernary("F?1:T?4:5"));
}

Đầu vào

"F?1:T?4:5"

Trình phân tích cú pháp biểu thức bậc ba trong C ++

Ví dụ (C ++)

Đầu vào

Đầu ra