利用栈求逻辑运算表达式的真值

2019-04-13 12:02发布

站内文章 / 模拟电子
17526 0 1637
今天浙江理工校赛的D题。 比赛结束后在网上看了文章才做出来的。

Problem D: 逻辑运算

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 248  Solved: 36

Description

 还记得大学里学过的模电么，今天就让我们将与或非变成一道题吧。 给你一个与或非的表达式，求出这个表达式的值，表达式总共有八种字符。 三种逻辑运算符按照优先级排列如下。 ‘！’：表示取反。 ‘&’：逻辑与。 ‘|’：逻辑或。 两个字符‘T’，‘F‘分别表示true和 false。 另外还有左右括号，空格三种字符。跟一般的表达式一样，括号可以改变优先级。  

Input

每组数据输入一行字符串,字符串长度小于等于100.

Output

 输出一个数0或1，表示逻辑表达式的答案。

Sample Input

T

Sample Output

1
用2个栈，一个存储运算符，一个存储运算的数字。 对于连个相继出现的操作符θ1和θ2 有三种关系：大于、等于和小于。由此可以列出“+-*/”之间的优先级。如下表：
     !      &     |      (      )      #
 !    >     >     >     <     >     >
 &   <     >     >     <     >     >
 |    <     <     >     <     >     >
 (    <     <     <     <     =     >
 )    >     >     >     <     >     >
 #   <     <     <     <     >     =
为了算法简洁，在表达式的左边和右边虚设一个“#”，这一对“#”表示一个表达式求值完成。 “（”    =     “）”  当一对括号相遇时表示括号内已运算完成。 “）”和“（”、“#”和“(”、“(”和“#”无法相继出现如果出现则表达式出现语法错误。 为实现优先算法，可以使用两个工作栈，一个是Q，用于寄存运算符，一个是P，用于寄存运算数和运算结果。

算法基本思路。

首先置操作数栈为空栈，表达式起始符为“#”为栈底元素。 依次读入表达式中的每个字符，若是操作数则进Q栈，若是运算符则和Q栈的栈顶运算符比较优先权作相应操作，直至整个表达式求值完毕（Q栈顶元素和当前读入的字符均为“#”）

代码实现：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const double PI = acos(-1.0);
const double e = 2.718281828459;
const double eps = 1e-8;
const int MAXN = 110;
char s[MAXN];
char opset[6] = {'!','&','|','(',')','#'};
char prio[6][6] =
{
    '>', '>', '>', '<', '>', '>',
    '<', '>', '>', '<', '>', '>',
    '<', '<', '>', '<', '>', '>',
    '<', '<', '<', '<', '=', '>',
    '>', '>', '>', '<', '>', '>',
    '<', '<', '<', '<', '>', '=',
};

//找到对应运算符在 opset 数组的下标
int findindex(char op)
{
    for(int i = 0; i < 6; i++)
    {
        if(opset[i] == op)
            return i;
    }
}

//比较Q栈顶元素与当前s[i]中运算符的优先级
char compare(char a, char b)
{
    int x = findindex(a);
    int y = findindex(b);
    return prio[x][y];
}

//计算 x y 在op运算符下的结果
int calc(int x, int y, char op)
{
    if(op == '|')
        return x|y;
    if(op == '&')
        return x&y;
    return 0;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    while(scanf("%s", s) != EOF)
    {
        int lens = strlen(s);
        s[lens] = '#';   // s 数组尾部存为'#'
        s[lens+1] = '

热门文章