Máy tính cơ bản III trong C ++

Giả sử chúng ta có một chuỗi biểu thức đơn giản và chúng ta phải Triển khai một máy tính cơ bản để đánh giá biểu thức đó. Chuỗi biểu thức có thể chứa dấu ngoặc mở và đóng ngoặc, dấu cộng + hoặc dấu trừ -, số nguyên không âm và khoảng trống. Chuỗi biểu thức chỉ chứa các số nguyên không âm, các toán tử +, -, *, /, mở và đóng ngoặc đơn và các khoảng trống. Phép chia số nguyên phải cắt ngắn về không.

Vì vậy, nếu đầu vào là "6-4 / 2", thì đầu ra sẽ là 4

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

l1:=0, l2:=1
o1:=1, o2:=1
Xác định một ngăn xếp
n:=kích thước của s
để khởi tạo i:=0, khi i
- x:=s [i]
- nếu x> ='0' và x <='9' thì -
  - num:=x - '0'
  - while (i + 1 ='0' and s [i + 1] <='9'), do -
    - (tăng i lên 1)
    - num:=(num * 10) + (s [i] - '0')
  - l2:=(nếu o2 giống 1 thì l2 * num, ngược lại l2 / num)
- ngược lại khi x giống với '(' thì -
  - chèn l1 vào st, chèn o1 vào st
  - chèn l2 vào st, chèn o2 vào st
  - l1:=0, o2:=1
  - o1:=1, l2:=1
- ngược lại khi x giống với ')' thì -
  - nhiệt độ:=l1 + o1 * l2
  - o2:=phần tử hàng đầu của st
  - xóa phần tử khỏi st
  - l2:=phần tử hàng đầu của st
  - xóa phần tử khỏi st
  - o1:=phần tử hàng đầu của st
  - xóa phần tử khỏi st
  - l1:=phần tử hàng đầu của st
  - xóa phần tử khỏi st
  - l2:=(nếu o2 giống 1 thì l2 * temp, ngược lại l2 / temp)
- ngược lại khi x giống với '*' hoặc x giống với '/' thì -
  - o2:=(nếu x giống với '*' thì là 1, ngược lại là -1)
- ngược lại khi x giống với '+' hoặc x giống với '-' thì -
  - nếu x giống với '-' và (i giống 0 hoặc (i - 1> =0 và s [i - 1] giống '(')), thì -
    - o1:=-1
    - Bỏ qua phần sau, chuyển sang phần tiếp theo
  - l1:=l1 + o1 * l2
  - o1:=(nếu x giống với '+' thì là 1, ngược lại là -1)
  - l2:=1, o2:=1
trả về l1 + o1 * l2

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

Ví dụ

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   int calculate(string s) {
      lli l1 = 0;
      lli l2 = 1;
      lli o1 = 1;
      lli o2 = 1;
      stack<lli> st;
      lli n = s.size();
      for (lli i = 0; i < n; i++) {
         char x = s[i];
         if (x >= '0' && x <= '9') {
            lli num = x - '0';
            while (i + 1 < n && s[i + 1] >= '0' && s[i + 1] <= '9') {
               i++;
               num = (num * 10) + (s[i] - '0');
            }
            l2 = (o2 == 1) ? l2 * num : l2 / num;
         }
         else if (x == '(') {
            st.push(l1);
            st.push(o1);
            st.push(l2);
            st.push(o2);
            l1 = 0;
            o2 = 1;
            o1 = 1;
            l2 = 1;
         }
         else if (x == ')') {
            lli temp = l1 + o1 * l2;
            o2 = st.top();
            st.pop();
            l2 = st.top();
            st.pop();
            o1 = st.top();
            st.pop();
            l1 = st.top();
            st.pop();
            l2 = (o2 == 1) ? l2 * temp : l2 / temp;
         }
         else if (x == '*' || x == '/') {
            o2 = (x == '*') ? 1 : -1;
         }
         else if (x == '+' || x == '-') {
            if (x == '-' && (i == 0 || (i - 1 >= 0 && s[i - 1] == '('))) {
               o1 = -1;
               continue;
            }
            l1 += o1 * l2;
            o1 = (x == '+') ? 1 : -1;
            l2 = 1;
            o2 = 1;
         }
      }
      return l1 + o1 * l2;
   }
};
main(){
   Solution ob;
   cout << (ob.calculate("(5+9*3)/8"));
}

Đầu vào

"(5+9*3)/8"

Máy tính cơ bản III trong C ++

Ví dụ

Đầu vào

Đầu ra