[Thuật toán] Tính giá trị biểu thức

Phương pháp nghịch đảo Balan hoặc cây biểu thức sẽ làm cho các bạn mới học lúng túng.
Đây là một phương cực kỳ đơn giản các bạn có thể đọc hiểu và vận dụng được
Biểu thức đơn giản bao gồm 2 phép toán + và *
Vd: 2*5+3+4*3+2
Cách tính:
Nếu trong biểu thức có phép + thì lấy phần biểu thức đầu + phần biểu thức cuối
Ngược lại nếu trong biểu thức có phép * thì lấy phần đầu biểu thức * phần cuối biểu thức
Ngược lại biểu thức = chính số đó

Minh họa: “2*5+3+4*3+2” = “2*5″+”3+4*3+2” = 2*5+3+”4*3+2″= 2*5+3+”4*3″+2 = 2*5+3+4*3+2
Biểu thức bao gồm các phép toán +, -, *
Trước khi tính biểu thức ta thêm vào dấu + trước mỗi dấu – (nếu có dấu – đứng đầu câu thì để nguyên)
Tính toán bình thường như không có phép –
Biểu thức bao gồm phép toán +, -, *, /
Thêm + vào trước –
Thêm * vào trước /
Trong lúc đổi xâu thành số nếu có lỗi thì cắt bỏ ký tự đầu của xâu -> tiếp tục đổi xâu thành số và sau đó lấy nghịch đảo. Tiến hành tính toán bình thường như biểu thức chỉ có + và *

Nếu bạn sử dụng giải thuật này trong bài viết bạn, làm ơn ghi rõ tên tác giả của giải thuật qvluom

Code minh họa với 4 phép toán +, -, *, /

#include <sstream>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <string>
using namespace std;

int check_to_number(string s) //kiem tra la so
{
	int check = 1, l = s.length();
	for (int i = 1; i<l; i++)
		if (!isdigit(s[i]) && s[i] != '.') //duyt tu phan tu thu 2neu khong la so hoac thi check = 0
		{
			check = 0;
			break;
		}
	if (s[0] == '-' && check == 1) return 2; //kiem tra dau xau co la -
	if (s[0] == '/' && check == 1) return 3; //kiem tra  dau xau co la /
	if (isdigit(s[0]) && check == 1) return 1; //dau xau la so
}

float convert_to_number(string s)
{
	float number, check = check_to_number(s);
	if (check > 0)
	{
		if (check == 1)  //neu la so binhf thuong
		{
			stringstream ss (s);
			ss >> number;
		}
		if (check > 1)
		{
			stringstream ss (s.substr(1,s.length()-1));
			ss >> number;
			if (check == 2) number = 0 - number; //neu la phep tru
			if (check == 3) number = 1/number; // neu la phep chia
		}
		return number;
	}
}

float process(string s, int l, int r)
{
	int li = 0, ri = r;
	if (check_to_number(s))  return convert_to_number(s); //{ cout <<"  "<<convert_to_number(s)<<endl; return convert_to_number(s);}
	else
	{
		int i;
		for (i=li; i<ri; i++) if (s[i] == '+') return process(s.substr(li, i-li), li, i) + process(s.substr(i+1, ri-i), i+1, ri-i);
		for (i=li; i<ri; i++) if (s[i] == '*') return process(s.substr(li, i-li), li, i) * process(s.substr(i+1, ri-i), i+1, ri-i);
	}
	return 0;
}

int main()
{
	float number;
	string s;
	getline(cin,s);
	for (int i=0; i<s.length(); i++)
	{
		if(s[i] == '-') { s.insert(i,"+"); i++; }
		if(s[i] == '/') { s.insert(i,"*"); i++; }
	}
	cout<<s<<endl;
	number = process(s,0,s.length());
	cout<<number<<endl;
	return 0;
}