fork download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. //#include <stdio.h>
  3. //#include <conio.h>
  4. //#include <stdlib.h>
  5. //#include <math.h>
  6. //#include <limits.h>
  7. //#include <time.h>
  8. //#include <string.h>
  9. //#include <windows.h>
  10. #include <iostream>
  11. #include <stack>
  12. //#include <queue>
  13. //#include <list>
  14. //#include <iterator> // advance()
  15. //#include <map>
  16. #include <string>
  17. //#include <Windows.h>
  18. //#include <cstring>
  19. //#include <iomanip>
  20. #include <algorithm>
  21. #include <vector>
  22. #include <fstream>
  23. //#include <ctime>
  24. //#include <cstdlib>
  25. /*
  26. 	KÝ PHÁP NGHỊCH ĐẢO BA LAN (REVERSE POLISH NOTATION)
  27. I. Chuẩn bị:
  28.  1. Hàm trả về độ ưu tiên của các toán tử (GetPriority)
  29.  2. Hàm chuẩn hóa chuỗi (xóa hết các khoảng trắng) (DeleteSpace)
  30.  3. Hàm phân biệt toán tử, toán hạng và ký tự mở ngoặc & đóng ngoặc (operatorType)
  31.  4. Hàm xử lý (gồm mảng Output và Stack)
  32. II. Chuyển đổi biểu thức trung tố sang hậu tố: Quy tắc
  33.  1. Nếu là toán hạng, ta add vào mảng Output.
  34.  2. Nếu là toán tử:
  35.   a) Thực hiện vòng lặp kiểm tra, nếu toán tử ở đỉnh stqck có độ ưu tiên >= toán tử hiện tại thì ta Pop toán
  36.   tử đó ra khỏi Stack và Push vào mảng Output
  37.   b) Push toán tử hiện tại vào Stack
  38.  3. Nếu là ký tử mở ngoặc, push vào stack.
  39.  4. Nếu là ký tự đóng ngoặc, ta Pop các phần tử trong Stack vào mảng Output cho đến khi gặp ký tự mở ngoặc
  40.  (nhớ là phải Pop luôn ký tự mở ngoặc đó nhưng không push vào mảng Output)
  41.  5. Hoàn tất vòng lặp, nếu trong stack vẫn còn phần tử thì ra lần lượt Pop các phần tử đó ra khỏi stack và
  42.  Push vào mảng Output.
  43.  6. Mảng Output chính là biểu thức hậu tố thu được.
  44. III. Tính toán dựa trên biểu thức hậu tố: Dùng vòng lặp duyệt mảng Output vừa tìm được
  45.  1. Nếu gặp toán hạng, Pop toán hạng đó khỏi Output và push vào Stack.
  46.  2. Nếu gặp toán tử, ta Pop 2 toán hạng khỏi Stack và tính toán dựa trên toán tử (nhớ là đúng thứ tự) và push
  47.  lại vào Stack.
  48.  3. Kết thúc vòng lặp, phần tử duy nhất trong Stack chính là kết quả.
  49. */
  50.  
  51. enum OperatorType { OPERAND, PARENTHESES, OPERATOR }; // toán hạng, cặp ngoặc và toán tử
  52. int getPriority(char); // trả về độ ưu tiên của các toán tử
  53. void DeleteSpace(std::string &); // xóa hết khoảng trắng trong chuỗi
  54. OperatorType operatorType(char); // phân biệt toán tử, toán hạng với cặp ngoặc
  55. std::vector<std::string> ConvertToPostfix(std::string); // chuyển biểu thức trung tố sang hậu tố
  56. double Calculate(std::string); // tính toán kết quả dựa trên biểu thức hậu tố
  57.  
  58. int main()
  59. { // INPUT.txt : (13 + (25 * 7 - 6 / 3) / (18^3 + 65 * 8 / 4) + 69)^2
  60. 	std::fstream FileIn("INPUT.txt", std::ios::in);
  61. 	std::string str;
  62. 	std::getline(FileIn, str);
  63. 	double result = Calculate(str);
  64. 	std::cout << str << " = " << result << std::endl;
  65. 	FileIn.close(); // Lưu ý là hàm hủy (destructor) lớp fstream trong C++ tự động close giùm.
  66. 	system("pause");
  67. 	return 0;
  68. }
  69. std::vector<std::string> ConvertToPostfix(std::string str)
  70. {
  71. 	DeleteSpace(str); // xóa hết các khoảng trắng
  72. 	std::vector<std::string> Output; // Lưu biểu thức hậu tố
  73. 	std::stack<char> Stack; // Lưu các toán tử và cặp ngoặc
  74. 	std::string number; // Lưu toán hạng
  75. 	int length = str.length();
  76. 	for (int i = 0; i < length; ++i) {
  77. 		char character = str[i];
  78. 		if (operatorType(character) == OPERAND)
  79. 			number.push_back(character);
  80. 		else {
  81. 			if (number.length() > 0) {
  82. 				Output.push_back(number); // Lưu toán hạng vào mảng Output
  83. 				number.clear(); // reset lại string number
  84. 			}
  85. 			if (operatorType(character) == PARENTHESES) {
  86. 				if (character == '(')
  87. 					Stack.push(character); // Lưu ký tự mở ngoặc vào Stack
  88. 				else if (character == ')') {
  89. 					while (Stack.top() != '(') {
  90. 						Output.push_back(std::string(1, Stack.top())); // Đây gọi là fill constructor
  91. 						//Output.emplace_back(1, Stack.top()); // Công dụng giống trên và thuộc C++11
  92. 						Stack.pop();
  93. 					}
  94. 					Stack.pop();
  95. 				}
  96. 			}
  97. 			if (operatorType(character) == OPERATOR) {
  98. 				// Nếu stack vẫn "đặc" và toán tử tại đỉnh Stack có độ ưu tiên lớn hơn toán tử đang xét
  99. 				while (!Stack.empty() && getPriority(Stack.top()) >= getPriority(character)) {
  100. 					Output.push_back(std::string(1, Stack.top())); // Đây gọi là fill constructor
  101. 					//Output.emplace_back(1, Stack.top()); // Công dụng giống trên và thuộc C++11
  102. 					Stack.pop();
  103. 				}
  104. 				Stack.push(character);
  105. 			}
  106. 		}
  107. 	}
  108. 	// Nếu string number vẫn "đặc"
  109. 	if (!number.empty()) {
  110. 		Output.push_back(number);
  111. 		number.clear();
  112. 	}
  113. 	// Nếu trong Stack vẫn còn thì Pop ra và Push vào mảng Output
  114. 	while (!Stack.empty()) {
  115. 		Output.push_back(std::string(1, Stack.top())); // Đây gọi là fill constructor
  116. 		//Output.emplace_back(1, Stack.top()); // Công dụng giống trên và thuộc C++11
  117. 		Stack.pop();
  118. 	}
  119. 	return Output;
  120. }
  121. double Calculate(std::string str)
  122. {
  123. 	std::vector<std::string> Output = ConvertToPostfix(str);
  124. 	std::stack<std::string> Stack;
  125. 	int size = Output.size();
  126. 	for (int i = 0; i < size; ++i) {
  127. 		// Nếu là toán hạng
  128. 		if (operatorType(Output[i][0]) == OPERAND) {
  129. 			Stack.push(Output[i]);
  130. 			Output.erase(Output.begin() + i); // Pop toán hạng đó ra khỏi mảng Output
  131. 			--size; // update lại size
  132. 			--i;
  133. 		}
  134. 		else if (operatorType(Output[i][0]) == OPERATOR) {
  135. 			char _char = Output[i][0];
  136. 			double operand2 = std::stof(Stack.top()); // convert string sang float
  137. 			Stack.pop();
  138. 			double operand1 = std::stof(Stack.top()); // convert string sang float
  139. 			Stack.pop();
  140. 			if (_char == '+')
  141. 				Stack.push(std::to_string(operand1 + operand2)); // convert float sang string
  142. 			else if (_char == '-')
  143. 				Stack.push(std::to_string(operand1 - operand2)); // convert float sang string
  144. 			else if (_char == '*')
  145. 				Stack.push(std::to_string(operand1 * operand2)); // convert float sang string
  146. 			else if (_char == '/')
  147. 				Stack.push(std::to_string(operand1 / operand2)); // convert float sang string
  148. 			else if (_char == '^')
  149. 				Stack.push(std::to_string(powf(operand1, operand2))); // convert float sang string
  150. 		}
  151. 	}
  152. 	return std::stof(Stack.top());
  153. }
  154. int getPriority(char ope)
  155. {
  156. 	if (ope == '^')
  157. 		return 3; // dấu mũ
  158. 	else if (ope == '*' || ope == '/')
  159. 		return 2; // dấu nhân hoặc chia
  160. 	else if (ope == '+' || ope == '-')
  161. 		return 1; // dấu cộng hoặc trừ
  162. 	else
  163. 		return 0;
  164. }
  165. void DeleteSpace(std::string &str)
  166. {
  167. 	str.erase(std::remove(str.begin(), str.end(), ' '), str.end()); // dịch các khoảng trắng về cuối chuỗi và xóa
  168. }
  169. OperatorType operatorType(char ope)
  170. {
  171. 	if (getPriority(ope) == 0) {
  172. 		if (ope != '(' && ope != ')')
  173. 			return OPERAND;
  174. 		else
  175. 			return PARENTHESES;
  176. 	}
  177. 	return OPERATOR;
  178. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In function ‘double Calculate(std::__cxx11::string)’:
prog.cpp:149:54: error: ‘powf’ was not declared in this scope
     Stack.push(std::to_string(powf(operand1, operand2))); // convert float sang string
                                                      ^
stdout
copy 
Standard output is empty
https://ideone.com/m1tTbI
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!