Basic Calculator II

題目

思路

和這個一樣：Basic Calculator I

代碼

class ExpressionTransformation { public:string trans_to_postfix_expression_to_s(string); // 將得到的表達式轉化為后綴表達式long long int calculate_from_postfix_expression(); // 依據后綴表達式計算值private:vector<string> ans_vector_post; // 存放后綴表達式string post_string; // 存放后綴表達式 };inline int prior(char op) { // 計算優先級函數if (op == '+' || op == '-') {return 1;}else if (op == '*' || op == '/' || op == '%') {return 2;}else {return 0;} }long long int string_to_int(string in) { // 將輸入的字符串轉化為對應數字函數char s[50];for (int i = 0; i < 50; i++) {s[i] = '\0';}for (int i = 0; i < in.size(); i++) {s[i] = in[i];}long long int ans;sscanf(s, "%lld", &ans);return ans; }string deleteBlank(string in) {string ans;int size = in.size();for (int i = 0; i < size; i++) {if (in[i] != ' ') ans.push_back(in[i]);}return ans; }string ExpressionTransformation::trans_to_postfix_expression_to_s(string in) {stack<char> op; // 操作符棧ans_vector_post.clear(); // 后綴表達式存放數組for (int i = 0; i < in.size();) {char c = in[i];if ('0' <= c && c <= '9') { // 是數字直接插入string num;int j;for (j = i; j < in.size() && '0' <= in[j] && in[j] <= '9'; j++) {num.push_back(in[j]);}ans_vector_post.push_back(num);i = j;}else {if (c == '(') { // 是開括號直接插入op.push('(');}else {if (c == ')') { // 是閉括號就把原本棧中的運算符都輸出，直到遇到開括號，注意開括號要丟棄while (op.top() != '(') {string temp;temp.push_back(op.top());ans_vector_post.push_back(temp);op.pop();}op.pop();}else { // 假如是加減乘除取余if (op.empty()) { // 操作符棧是空就直接插入op.push(c);}else { // 假設掃描到的運算符優先級高于棧頂運算符則，把運算符壓入棧。否則的話，就依次把棧中運算符彈出加到數組ans的末尾，直到遇到優先級低于掃描到的運算符或棧空。而且把掃描到的運算符壓入棧中if (prior(c) > prior(op.top())) {op.push(c);}else {while (!op.empty() && prior(c) <= prior(op.top())) {string temp;temp.push_back(op.top());ans_vector_post.push_back(temp);op.pop();}op.push(c);}}}}i++;}}while (!op.empty()) { // 注意把操作符棧中的剩余操作符輸出string temp;temp.push_back(op.top());ans_vector_post.push_back(temp);op.pop();}post_string.clear(); // 構造string并返回for (int i = 0; i < ans_vector_post.size(); i++) {post_string += ans_vector_post[i];}return post_string; }long long int ExpressionTransformation::calculate_from_postfix_expression() {//利用棧對后綴表達式求值。直接從后綴表達式的左往右掃描。遇到數字放入棧中，遇到字符就把棧頂的兩個數字拿出來算。然后再放進棧stack<long long int> ans_post;for (int i = 0; i < ans_vector_post.size(); i++) {long long int x, y;if ('0' <= ans_vector_post[i][0] && ans_vector_post[i][0] <= '9') {ans_post.push(string_to_int(ans_vector_post[i]));}else {y = ans_post.top(); // 注意順序，這里好比xy+就是x+yans_post.pop();x = ans_post.top();ans_post.pop();if (ans_vector_post[i][0] == '+') {ans_post.push(x + y);}else if (ans_vector_post[i][0] == '-') {ans_post.push(x - y);}else if (ans_vector_post[i][0] == '*') {ans_post.push(x * y);}else if (ans_vector_post[i][0] == '/') {ans_post.push(x / y);}else {ans_post.push(x % y);}}}return ans_post.top(); }class Solution { public:int calculate(string s) {ExpressionTransformation e;s = deleteBlank(s);e.trans_to_postfix_expression_to_s(s);int postAns = e.calculate_from_postfix_expression();return postAns;} };

總結

以上是生活随笔為你收集整理的LeetCode OJ Basic Calculator II的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。