算符优先分析法
发布网友
发布时间：2022-05-01 02:17
共1个回答
热心网友
时间：2022-06-22 09:35
#include <iostream>
#include <string>
using namespace std;
#define MAX 30//栈容量
#define INPUTMAX 60//键盘接收字符允许的最大个数
int F( char );//进栈优先函数
int G( char );//比较优先函数
//函数重载Push、Pop
void Push( int );//Stack1进栈函数
void Push( char );//Stack2进栈函数
int Pop( int );//Stack1出栈函数
void Pop( char );//Stack2出栈函数
int Stack1[MAX];//操作数栈
int m;//栈Stack1指针
char Stack2[MAX];//运算符栈
int n;//栈Stack2指针
void main()
{
int i = 1;//键盘接收字符定位
m = 0;//栈指针初始化
n = 0;//栈指针初始化
char ch[INPUTMAX];//定义接收字符数组
cout << "请输入符号串(括在两个#之间):" << endl;
cin >> ch;
int len = strlen( ch );//统计字符长度
if( ch[0] != '#' || ch[len-1] != '#' )
cout << "符号串必须在两个#之间!" << endl;
else
{
cout << "///////////////////" << endl;
cout << "Stack1为操作数栈!" << endl;
cout << "Stack2为运算符栈!" << endl;
cout << "///////////////////" << endl;
cout << "栈操作如下:" << endl;
cout << "///////////////////" << endl;
Push( ch[0] );//将字符串首字符压进栈
cout << "Stack2: " << Stack2[0] << "进栈!" << endl;
while(i < len)
{
if( ch[i] >= '0' && ch[i] <= '9' )//判断位数
{
int value = 0;
while( ch[i] >= '0' && ch[i] <= '9' )//字符数字串转换为十进制数
{
value = value * 10;
value = value + (ch[i]-48);
i++;
}
Push( value );//将最终的数字压入栈
cout << "Stack1: " << value << "进栈!" << endl;
}
else
{
if( F(Stack2[n-1]) <= G(ch[i]) )//当前字符优先级小于下一字符优先级则把下一字符压进栈
{
jmp: Push( ch[i] );
cout << "Stack2: " << Stack2[n-1] << "进栈!" << endl;
}
else//当前字符优先级小于下一字符优先级
{
int j;
for(j = n-1;j >= 1;j--)//循环处理栈Stack2字符
{
if(Stack2[j] == '+')//栈顶运算符为'+'则执行加法运算
{
int t1,t2,t3;
cout << "Stack1: " << Stack1[m-1] << "出栈!" << endl;//将操作数栈顶上的两个操作数做出栈处理
t1 = Pop( Stack1[m-1] );
cout << "Stack1: " << Stack1[m-1] << "出栈!" << endl;
t2 = Pop( Stack1[m-1] );
t3 = t1 + t2;//根据运算符栈顶的运算符运算
Push( t3 );//将运算结果压进操作数栈
cout << "Stack1: " << Stack1[m-1] << "进栈!" << endl;
cout << "Stack2: " << Stack2[j] << "出栈!" << endl;
Pop( Stack2[j] );//将运算符栈顶的运算符做出栈处理
if( F(Stack2[j-1]) <= G(ch[i]) )//若栈内下一字符优先级小于字符串字符优先级则跳至jmp将其压栈同时跳出此循环否则出错
goto jmp;
}
else if(Stack2[j] == '-')//栈顶运算符为'-'则执行减法运算
{
int t1,t2,t3;
cout << "Stack1: " << Stack1[m-1] << "出栈!" << endl;//将操作数栈顶上的两个操作数做出栈处理
t1 = Pop( Stack1[m-1] );
cout << "Stack1: " << Stack1[m-1] << "出栈!" << endl;
t2 = Pop( Stack1[m-1] );
t3 = t2 - t1;//根据运算符栈顶的运算符运算
Push( t3 );//将运算结果压进操作数栈
cout << "Stack1: " << Stack1[m-1] << "进栈!" << endl;
cout << "Stack2: " << Stack2[j] << "出栈!" << endl;
Pop( Stack2[j] );//将运算符栈顶的运算符做出栈处理
if( F(Stack2[j-1]) <= G(ch[i]) )//若栈内下一字符优先级小于字符串字符优先级则跳至jmp将其压栈同时跳出此循环否则出错
goto jmp;
}
else if(Stack2[j] == '*')//栈顶运算符为'*'则执行乘法运算
{
int t1,t2,t3;
cout << "Stack1: " << Stack1[m-1] << "出栈!" << endl;//将操作数栈顶上的两个操作数做出栈处理
t1 = Pop( Stack1[m-1] );
cout << "Stack1: " << Stack1[m-1] << "出栈!" << endl;
t2 = Pop( Stack1[m-1] );
t3 = t1 * t2;//根据运算符栈顶的运算符运算
Push( t3 );//将运算结果压进操作数栈
cout << "Stack1: " << Stack1[m-1] << "进栈!" << endl;
cout << "Stack2: " << Stack2[j] << "出栈!" << endl;
Pop( Stack2[j] );//将运算符栈顶的运算符做出栈处理
if( F(Stack2[j-1]) <= G(ch[i]) )//若栈内下一字符优先级小于字符串字符优先级则跳至jmp将其压栈同时跳出此循环否则出错
goto jmp;
}
else if(Stack2[j] == '/')//栈顶运算符为'/'则执行除法运算
{
int t1,t2,t3;
cout << "Stack1: " << Stack1[m-1] << "出栈!" << endl;//将操作数栈顶上的两个操作数做出栈处理
t1 = Pop( Stack1[m-1] );
cout << "Stack1: " << Stack1[m-1] << "出栈!" << endl;
t2 = Pop( Stack1[m-1] );
t3 = t2 / t1;//根据运算符栈顶的运算符运算
Push( t3 );//将运算结果压进操作数栈
cout << "Stack1: " << Stack1[m-1] << "进栈!" << endl;
cout << "Stack2: " << Stack2[j] << "出栈!" << endl;
Pop( Stack2[j] );//将运算符栈顶的运算符做出栈处理
if( F(Stack2[j-1]) <= G(ch[i]) )//若栈内下一字符优先级小于字符串字符优先级则跳至jmp将其压栈同时跳出此循环否则出错
goto jmp;
}
else if(Stack2[j] == '^')//栈顶运算符为'^'则执行幂运算
{
int t1,t2,t3 = 1;
cout << "Stack1: " << Stack1[m-1] << "出栈!" << endl;//将操作数栈顶上的两个操作数做出栈处理
t1 = Pop( Stack1[m-1] );
cout << "Stack1: " << Stack1[m-1] << "出栈!" << endl;
t2 = Pop( Stack1[m-1] );
for( int t = 0;t < t1;t++)//根据运算符栈顶的运算符运算
t3 = t3 * t2;
Push( t3 );//将运算结果压进操作数栈
cout << "Stack1: " << Stack1[m-1] << "进栈!" << endl;
cout << "Stack2: " << Stack2[j] << "出栈!" << endl;
Pop( Stack2[j] );//将运算符栈顶的运算符做出栈处理
if( F(Stack2[j-1]) <= G(ch[i]) )//若栈内下一字符优先级小于字符串字符优先级则跳至jmp将其压栈同时跳出此循环否则出错
goto jmp;
}
else
{
cout << "Stack2: " << Stack2[j] << "出栈!" << endl;
Pop( Stack2[j] );
}
}
Push( ch[i] );//将字符串最后的字符压进栈
cout << "Stack2: " << ch[i] << "进栈!" << endl;
}
i++;//读下一字符继续循环
}
}
cout << "///////////////////" << endl;
if(Stack2[0] == Stack2[1])//若栈尾的最后两个字符都为#则分析成功
{
cout << "算符优先分析成功!" << endl;
cout << "///////////////////" << endl;
cout << "运算结果:" << Stack1[m-1] << endl;//根据算符优先将结果输出
cout << "///////////////////" << endl;
}
else
cout << "算符优先分析失败!" << endl;
}
}
int F( char ch )//进栈优先函数
{
if( ch == ')' )
return 9;
else if( ch == '^' )
return 7;
else if( ch == '*' || ch == '/' )
return 5;
else if( ch == '+' || ch == '-' )
return 3;
else if( ch == '(' )
return 1;
else
return 0;
}
int G( char ch )//比较优先函数
{
if( ch == ')' )
return 1;
else if( ch == '^' )
return 6;
else if( ch == '*' || ch == '/' )
return 4;
else if( ch == '+' || ch == '-' )
return 2;
else if( ch == '(' )
return 8;
else
return 0;
}
void Push( int num )
{
if( m >= MAX )//m大于MAX时栈满
cout << "栈满!" << endl;
else
Stack1[m++] = num;//压栈后栈序号加1
}
void Push( char ch )
{
if( n >= MAX )//n大于MAX时栈满
cout << "栈满!" << endl;
else
Stack2[n++] = ch;//压栈后栈序号加1
}
int Pop( int num )
{
if( m <= 0 )//m小于零时栈空
cout << "栈空!" << endl;
else
num = Stack1[--m];//出栈后栈序号减1
return num;
}
void Pop( char ch )
{
if( n <= 0 )//n小于零时栈空
cout << "栈空!" << endl;
else
ch = Stack2[--n];//出栈后栈序号减1
}
参考资料：http://zhidao.baidu.com/question/55305509.html?si=2&wtp=wk
