题目:
输入一个简单的算术表达式,并以“#”号结束。利用栈来实现算术表达式求值的算法
输出结果:
主要算法:
char EvaluateExpression()
{//算术表达式求值的算符优先算法,设OPTR和OPND分别为运算符栈和操作数栈
LinkStack OPND, OPTR;
InitStack(OPND); //初始化OPND栈
InitStack(OPTR); //初始化OPTR栈
Push(OPTR,'#'); //将表达式起始符"#"压入OPTR栈
char ch;
cin >> ch;
while (ch != '#' || GetTop(OPTR) != '#') //表达式没有查找完毕或运算符栈的栈顶元素不为"#"
{
if (!In(ch)) {
Push(OPND, ch); //ch不是运算符就进操作数栈
cin >> ch;
}
else //ch是运算符
switch (Precede(GetTop(OPTR), ch)) //就比较运算符栈的栈顶元素和ch的优先级
{
case'<': //运算符栈顶元素优先级小,则将当前字符压入运算符栈
Push(OPTR, ch);
cin >> ch; //读入下一字符ch。
break;
case'>': //运算符栈顶元素优先级大,
char theta, b, a;
Pop(OPTR, theta); //弹出运算符栈顶的运算符,
Pop(OPND, b); //弹出操作数栈顶的两个运算数,
Pop(OPND, a);
Push(OPND, Operate(a, theta, b));//将运行结果压入操作数栈。
break;
case'=': //运算符栈的栈顶元素是"("且ch是")",
char t;
Pop(OPTR,t); //弹出运算符栈顶的"(",
cin >> ch; //读入下一字符。
break;
}
}
return GetTop(OPND);//操作数栈顶元素即是表达式求值结果
}
完整代码:
#include<iostream>
using namespace std;
typedef struct StackNode
{
char data;
struct StackNode *next;
}StackNode,*LinkStack;
int InitStack(LinkStack& S)
{
S = NULL;
return 1;
}
int Push(LinkStack& S, char e)
{
LinkStack p = new StackNode;
if (!p)
exit(OVERFLOW);
p->data = e;
p->next = S;
S = p;
return 1;
}
char GetTop(LinkStack& S)
{
if (S == NULL)
exit(1);
else
return S->data;
}
int Pop(LinkStack& S, char& e)
{
if (S == NULL)
return 0;
e = S->data;
LinkStack p = S;
S = S->next;
delete p;
return 1;
}
int In(char ch) {
if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')' || ch == '#')
return 1;
else
return 0;
}
char Precede(char ch1, char ch2)
{
char operation{};
switch (ch1)
{
case'+':
case'-':if (ch2 == '+' || ch2 == '-'||ch2==')'||ch2=='#')
operation = '>';
else
operation = '<';
break;
case'*':
case'/':if (ch2 == '(' )
operation = '<';
else
operation = '>';
break;
case'(':if (ch2 == ')')
operation = '=';
else
operation = '<';
break;
case')':
operation = '>';
break;
case'#':
operation = '<';
break;
}
return operation;
}
char Operate(char a, char operation, char b)
{
char result{};
switch (operation)
{
case'+':result= (a-'0') + (b-'0')+'0';
break;
case'-':result = (a - '0') -(b - '0')+'0';
break;
case'*':result = (a - '0') * (b - '0')+'0';
break;
case'/':result = (a - '0') / (b - '0')+'0';
break;
}
return result;
}
char EvaluateExpression()
{
LinkStack OPND, OPTR;
InitStack(OPND);
InitStack(OPTR);
Push(OPTR,'#');
char ch;
cin >> ch;
while (ch != '#' || GetTop(OPTR) != '#')
{
if (!In(ch)) {
Push(OPND, ch);
cin >> ch;
}
else
switch (Precede(GetTop(OPTR), ch))
{
case'<':
Push(OPTR, ch);
cin >> ch;
break;
case'>':
char theta, b, a;
Pop(OPTR, theta);
Pop(OPND, b);
Pop(OPND, a);
Push(OPND, Operate(a, theta, b));
break;
case'=':
char t;
Pop(OPTR,t);
cin >> ch;
break;
}
}
return GetTop(OPND);
}
int main() {
cout << "请输入一个算数表达式以#结尾:" << endl;
char r;
r = EvaluateExpression();
int s = r - '0';
cout << "结果为:" <<s;
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)