สมมติว่าเรามีสตริงนิพจน์ง่ายๆ และเราต้องนำเครื่องคำนวณพื้นฐานไปใช้เพื่อประเมินนิพจน์นั้น สตริงนิพจน์อาจมีวงเล็บเปิดและปิด เครื่องหมายบวก + หรือลบ - จำนวนเต็มไม่เป็นลบ และพื้นที่ว่าง สตริงนิพจน์ประกอบด้วยเฉพาะจำนวนเต็มไม่เป็นลบ, +, -, *, / โอเปอเรเตอร์, วงเล็บเปิดและปิด และพื้นที่ว่าง การหารจำนวนเต็มควรตัดให้เหลือศูนย์
ดังนั้นหากอินพุตเป็น "6-4 / 2" เอาต์พุตจะเป็น 4
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
l1 :=0, l2 :=1
-
o1 :=1, o2 :=1
-
กำหนดหนึ่งสแต็ก st
-
n :=ขนาดของ s
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
x :=s[i]
-
ถ้า x>='0' และ x <='9' แล้ว −
-
num :=x - '0'
-
ในขณะที่ (i + 1
='0' และ s[i + 1] <='9') ทำ - -
(เพิ่ม i ขึ้น 1)
-
num :=(num * 10) + (s[i] - '0')
-
-
l2 :=(ถ้า o2 เหมือนกับ 1 แล้ว l2 * num มิฉะนั้น l2 / num)
-
-
มิฉะนั้นเมื่อ x เหมือนกับ '(' แล้ว −
-
ใส่ l1 เข้าไปใน st ใส่ o1 เข้าไปใน st
-
ใส่ l2 เข้าไปใน st ใส่ o2 เข้าไปใน st
-
l1 :=0, o2 :=1
-
o1 :=1, l2 :=1
-
-
มิฉะนั้นเมื่อ x เหมือนกับ ')' ดังนั้น −
-
อุณหภูมิ :=l1 + o1 * l2
-
o2 :=องค์ประกอบด้านบนของ st
-
ลบองค์ประกอบออกจาก st
-
l2 :=องค์ประกอบด้านบนของ st
-
ลบองค์ประกอบออกจาก st
-
o1 :=องค์ประกอบด้านบนของ st
-
ลบองค์ประกอบออกจาก st
-
l1 :=องค์ประกอบด้านบนของ st
-
ลบองค์ประกอบออกจาก st
-
l2 :=(ถ้า o2 เหมือนกับ 1 แล้ว l2 * temp มิฉะนั้น l2 / temp)
-
-
มิฉะนั้นเมื่อ x เหมือนกับ '*' หรือ x เหมือนกับ '/' ดังนั้น −
-
o2 :=(ถ้า x เหมือนกับ '*' ให้เปลี่ยนเป็น 1 มิฉะนั้น -1)
-
-
มิฉะนั้นเมื่อ x เหมือนกับ '+' หรือ x เหมือนกับ '-' ดังนั้น −
-
ถ้า x เหมือนกับ '-' และ (i เท่ากับ 0 หรือ (i - 1>=0 และ s[i - 1] เหมือนกับ '(')) ดังนั้น −
-
o1 :=-1
-
ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป
-
-
l1 :=l1 + o1 * l2
-
o1 :=(ถ้า x เหมือนกับ '+' แล้ว 1 มิฉะนั้น -1)
-
l2 :=1, o2 :=1
-
-
-
กลับ l1 + o1 * l2
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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"));
} อินพุต
"(5+9*3)/8"
ผลลัพธ์
4
