简易计算器
- 问题描述：用c++实现一个能够进行加减乘除运算的简易计算器。输入包括int型、'+'、'-'、'*'、'/'、'('、')'，没有空格并以'='结尾的中序表达式。输出转化后的后续表达式和结果。
中序、后序表达式
- 中序表达式符合人的思维习惯从左至右接收运算数和运算符按顺序计算，但对于计算机来说较为复杂，一旦出现了括号将会改变算符实际计算过程中的优先级
例如：3*(2+2)+1
- 后序表达式因其没有括号、只需要单向扫描而更符合计算机的计算过程，将需要运算的数字依次入栈直到扫描到算符，则将存放运算数的栈弹出操作数进行操作，并将结果重新入栈作为新的操作数，直到表达式扫描结束，运算数栈中的元素就是最后的结果
将上述例子转化为后序表达式：3 2 2 + * 1 +
中序表达式转化为后序表达式
思路：因为计算机对于后序表达式是从左向右进行扫描，所以运算符实际运算中（考虑中序表达式中有括号的情况）的优先级决定了运算符在后序表达式中的位置。对于操作数没有所谓的优先级，所以遇到操作数直接输出为后序表达式元素即可。
-
运算符入栈：由于后序表达式中的运算符位于操作数的后边，所以在转化过程中应当先把运算符存放在一个栈中。
那么，弹出条件：- 操作数全部输出，中序表达式扫描结束，运算符依次弹出；
case '=':
while (!temp.empty())
{
calBefore.push_back(temp.top());
calBefore.push_back(' ');
temp.pop();
}
break;
- 新入栈元素优先级低于栈顶元素时，需要先将栈顶元素弹出为后序表达式元素，再将新运算符入栈，以保证后序表达式中的运算符顺序与计算优先级一致。
if (!temp.empty())
{
while (!temp.empty() && (temp.top() == '/' || temp.top() == '*'))
{
calBefore.push_back(temp.top());
calBefore.push_back(' ');
temp.pop();
}
}
temp.push(*it);
break;
- 括号处理：中序表达式中用括号改变了运算符的优先级，转化过程中，需要将括号当作运算符入栈以此区分括号内外运算符。
1.‘(’无条件入栈；- 扫描至‘)’时，需要不断将栈中元素弹出直至将‘(’弹出。注意：后序表达式中没有括号，括号不需要输出
举例说明：
根据上述例子 3*(2+2)+1 可以画出上图，左边是string类型的中序表达式，中间是stack类型存放运算符，右边是string类型用于输出的后序表达式。
按步骤操作至上图都不存在需要特殊处理的操作：操作数直接输出为后序表达式、运算符入栈，每次入栈的运算符都比栈顶元素优先级低（或相等）
2.中序表达式下一个元素为 ‘)’，应当将运算符栈在 ‘ (’之后入栈的元素全部弹出，此处只有一个元素为 “+”，则得到下图
3.接着下一个元素为 “+”，入栈发现优先级低于栈顶元素 “*”，则要将 “*”先弹出再入栈，得下图
4.下一个元素为“1”，直接输出。最后若运算符栈不为空全部弹出。
得到后序表达式为 3 2 2 + * 1 +。
由后序表达式计算结果
将中序表达式转化为后序表达式后，对于计算机来说计算就变得很简单了：
1.只需要从左往右扫描表达式，将操作数存入栈中等待运算
2.扫描到运算符就将操作数栈顶部两个操作数弹出参与运算，运算结果重新入栈作为新的操作数
3.如此执行，直到表达式扫描完成，操作数中的最后一个数就是计算结果
如图所示，将操作数入栈直至碰到运算符 ‘+’，此时将操作数栈顶部两个元素弹出，分别是 ‘2’、‘2’，运算结果 ‘4’ 重新入栈得下图
此时扫描至表达式中下一位 ‘ * ’，同样弹出操作数栈顶部两个元素分别是 ‘ 4 ’、‘ 3 ’，参与运算得到 ‘ 12 ’入栈，得下图
继续 ——‘ 1 ’入栈，得下图
扫描至 ‘+’ 号弹出操作数运算，得 ‘ 13 ’入栈，得下图
表达式扫描完毕，操作数栈中元素即为运算结果。
代码如下
int Calculation(string calstr)
{
stack<int> calnum;
string calBefore_ = calstr;
string::iterator it = calBefore_.begin();
while (!calBefore_.empty())
{
if (*it == 32) //读取空格
{
it = calBefore_.erase(calBefore_.begin());
continue;
}
else if (48 <= *it && *it <= 57)
{
string temp;
int i = 0;
while (48 <= *it && *it <= 57)
{
temp.push_back(*it);
it++;
i++;
}
while (i > 0)
{
it = calBefore_.erase(calBefore_.begin());
i--;
}
calnum.push(atoi(temp.c_str()));
continue;
}
else
{
switch (*it)
{
case '+':
calnum.push(Add(calnum));
break;
case '-':
calnum.push(Minus(calnum));
break;
case '*':
calnum.push(Mutiply(calnum));
break;
case '/':
calnum.push(Division(calnum));
break;
default:
cout << "Error!" << endl;
break;
}
it = calBefore_.erase(calBefore_.begin());
}
}
return calnum.top();
}
