Skip to content

Instantly share code, notes, and snippets.

@topin27

topin27/expression.cpp

Created September 17, 2012 02:52
Show Gist options
  • Save topin27/3735307 to your computer and use it in GitHub Desktop.
Save topin27/3735307 to your computer and use it in GitHub Desktop.
Download ZIP
华为的一道上机题，一个简单的计算算术表达式（带括号）的程序，没有使用传统的栈来解决。
Raw
expression.cpp
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <cstdlib>
using namespace std;
static int simple_arithmetic(const string &k_expression_) // No any brakets.
{
vector<int> nums;
vector<char> todo; // for all operational character.
vector<int>::iterator p_nums;
size_t len = k_expression_.size();
int tmp;
size_t i = 0, j = 0;
for (; i < len; ++i) {
if (k_expression_[i] == '*' || k_expression_[i] == '/' || \
k_expression_[i] == '-' || k_expression_[i] == '+') {
if (i != j) {
nums.push_back(atoi(k_expression_.substr(j, i - j).c_str()));
todo.push_back(k_expression_[i]);
j = i + 1;
continue;
}
else { // negative number.
nums.push_back(0 - atoi(k_expression_.substr(1).c_str()));
break;
}
}
}
nums.push_back(atoi(k_expression_.substr(j, i - j).c_str())); // to add the last numbers.
for (vector<char>::iterator i = todo.begin(); i != todo.end();) {
if (*i == '*') {
tmp = nums[i - todo.begin() + 1];
nums.erase(nums.begin() + (i - todo.begin()) + 1);
nums[i - todo.begin()] *= tmp;
i = todo.erase(i); // I can't erase current vector's element when I'm in it.
}
else if (*i == '/') {
tmp = nums[i - todo.begin() + 1];
nums.erase(nums.begin() + (i - todo.begin()) + 1);
nums[i - todo.begin()] /= tmp;
i = todo.erase(i);
}
else
i++;
}
for (vector<char>::iterator i = todo.begin(); i != todo.end();) {
if (*i == '+') {
tmp = nums[i - todo.begin() + 1];
nums.erase(nums.begin() + (i - todo.begin()) + 1);
nums[i - todo.begin()] += tmp;
i = todo.erase(i);
}
else if (*i == '/') {
tmp = nums[i - todo.begin() + 1];
nums.erase(nums.begin() + (i - todo.begin()) + 1);
nums[i - todo.begin()] -= tmp;
i = todo.erase(i);
}
else
i++;
}
return *nums.begin();
}
int parentheses_arithmetic(const string &k_expression_)
{
string expression(k_expression_);
string tmp("");
stringstream ss;
int rpos, lpos = 0;
rpos = expression.find(')');
while (rpos != string::npos) {
lpos = expression.rfind('(', rpos);
ss << simple_arithmetic(expression.substr(lpos + 1, rpos - lpos - 1));
tmp = ss.str();
ss.str(""); // clear the stringstream.
expression.replace(lpos, rpos - lpos + 1, tmp);
rpos = expression.find(')');
}
return simple_arithmetic(expression);
}
int main()
{
string ex = "(1+2+(3+4))+(5/6)";
cout << parentheses_arithmetic(ex) << endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment