Created
November 16, 2013 09:34
-
-
Save soulmachine/7498132 to your computer and use it in GitHub Desktop.
计算器,支持四则运算,小括号,整数,浮点数,暂时不支持16进制,正号,负号
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <string> | |
#include <stack> | |
#include <vector> | |
using namespace std; | |
bool is_operator(const char op) { | |
return string("+-*/").find(op) != string::npos; | |
} | |
// 获取操作符的优先级 | |
int get_priority(const char op) { | |
switch (op) { | |
case '#': | |
return -1; | |
case '(': | |
return 0; | |
case '+': | |
case '-': | |
return 1; | |
case '*': | |
case '/': | |
return 2; | |
default: | |
return -1; | |
} | |
} | |
// 将输入的中缀表达式进行格式化,清洗,非法处理等 | |
vector<string> format_input(const string& str) { | |
vector<string> result; | |
string num; | |
for (auto ch : str) { | |
if (::isdigit(ch) || ch == '.') { // 遇到数字和小数点直接写入后缀表达式 | |
num += ch; | |
} | |
else { | |
if (!num.empty()) { | |
result.push_back(num); | |
num.clear(); | |
} | |
result.push_back(string(1, ch)); | |
} | |
} | |
if (!num.empty()) { | |
result.push_back(num); | |
num.clear(); | |
} | |
return result; | |
} | |
// 将中缀表达式转换为后缀表达式 | |
vector<string> convert_to_postfix1(const vector<string> &infix) { | |
vector<string> result; | |
stack<char> s; // 操作符栈 | |
s.push('#'); // 首先把结束标志‘#’放入栈底 | |
for (auto str : infix) { | |
if (::isdigit(str.back())) { // 遇到数字直接写入后缀表达式 | |
result.push_back(str); | |
} | |
else if (str[0] == '(') result.push_back(str); // // 遇到“(”不用比较直接入栈 | |
else if (str[0] == ')') { // 遇到右括号将其对应左括号后的操作符(操作符栈中的)全部写入后缀表达式 | |
while (s.top() != '(') { | |
result.push_back(string(1, s.top())); | |
s.pop(); | |
} | |
s.pop(); // 将“(”出栈,后缀表达式中不含小括号 | |
} | |
else if (is_operator(str[0])) { | |
// 当前的操作符小于等于栈顶操作符的优先级时,将栈顶操作符写入到后缀表达式 | |
while (get_priority(str[0]) <= get_priority(s.top())) { | |
result.push_back(string(1, s.top())); | |
s.pop(); | |
} | |
s.push(str[0]); // 将该操作符入栈 | |
} | |
} | |
while (!s.empty()) { // 将所有的操作符加入后缀表达式 | |
result.push_back(string(1, s.top())); | |
s.pop(); | |
} | |
result.pop_back(); // 弹出 '#' | |
return result; | |
} | |
// 对逆波兰表达式进行求值 | |
double eval_rpn(vector<string> &rpn) { | |
double x, y; | |
auto tk = rpn.back(); rpn.pop_back(); | |
auto n = tk.size(); | |
if (n == 1 && is_operator(tk[0])) { | |
y = eval_rpn(rpn); | |
x = eval_rpn(rpn); | |
if (tk[0] == '+') x += y; | |
else if (tk[0] == '-') x -= y; | |
else if (tk[0] == '*') x *= y; | |
else x /= y; | |
} | |
else { | |
size_t i; | |
x = stod(tk, &i); | |
} | |
return x; | |
} | |
int main() { | |
string input; | |
cin >> input; | |
auto infix = format_input(input); | |
for (auto str : infix) { | |
cout << str << ' '; | |
} | |
cout << endl << endl; | |
auto postfix = convert_to_postfix1(infix); | |
for (auto str : postfix) { | |
cout << str << ' '; | |
} | |
cout << endl << eval_rpn(postfix) << endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment