#include <iostream>
#include <stack>
#include <cctype>
/**
* 获取优先级符号,flag数组优先级关系是根据oper得来的,所以它们中元素的顺序不能轻易改变
* @param a[in] 先前的运算符
* @param b[in] 之后的运算符
* @return 成功返回运算符,失败返回空格字符
*/
char Precede(char a, char b)
{
int i, x=-1, y=-1;
const char oper[7] = {'+', '-', '*', '/', '(', ')', '='};
const char flag[7][7] = {
'>', '>', '<', '<', '<', '>', '>',
'>', '>', '<', '<', '<', '>', '>',
'>', '>', '>', '>', '<', '>', '>',
'>', '>', '>', '>', '<', '>', '>',
'<', '<', '<', '<', '<', '=', ' ',
'>', '>', '>', '>', ' ', '>', '>',
'<', '<', '<', '<', '<', ' ', '='
};
for (i=0; i<7; i++)
{
if (oper[i] == a)
{
x = i;
break;
}
}
for (i=0; i<7; i++)
{
if (oper[i] == b)
{
y = i;
break;
}
}
if (-1!=x && -1!=y)
{
return flag[x][y];
}
return ' ';
}
/**
* 左右操作数求值
* @param x[in] 左边操作数
* @param theta[in] 运算符
* @param y[in] 右边操作数
* @return 成功返回运算结果,失败返回0
*/
int Operate(int x, char theta, int y)
{
int ret = 0;
switch (theta)
{
case '+':
ret = x+y;
break;
case '-':
ret = x-y;
break;
case '*':
ret = x*y;
break;
case '/':
ret = x/y;
break;
default:
break;
}
return ret;
}
/**
* 表达式求值,表达式以‘=’结束,如:2*(3+5)=
* @param str[in] 字符串表达式指针
* @return 最终结果
*/
int EvaluateExpression(const char *str)
{
char theta;
int x, y;
const char *left;
const char *right;
char tmp[16];
std::stack<int> opnd;
std::stack<char> optr;
optr.push('=');
while ((*str)!='=' || optr.top()!='=')
{
left = str;
if (isdigit(*left))
{
while (isdigit(*(++str)));
right = str;
memset(tmp, 0, sizeof(tmp));
strncpy(tmp, left, right-left);
opnd.push(atoi(tmp));
}
else if (isspace(*left))
{
++str;
}
else
{
switch (Precede(optr.top(), *left))
{
case '<':
optr.push(*left);
++str;
break;
case '=':
optr.pop();
++str;
break;
case '>':
theta = optr.top();
optr.pop();
y = opnd.top();
opnd.pop();
x = opnd.top();
opnd.pop();
opnd.push(Operate(x, theta, y));
break;
default:
break;
}
}
}
return opnd.top();
}
int main()
{
int last = EvaluateExpression("20*(12+8)+100=");
std::cout << last << std::endl;
return 0;
}
表达式求值——栈
Published: at 01:57 PM | 3 min read